# CS50 Week 3: Algorithms

On algorithms, Big O notation and other difficult stuff that I forgot the moment I learned😅.

## Linear search permalink

Iterate across the array from left to right, trying to find the target element.

`O(n)`

- on the order of n

`for i from 0 to n-1`

If i-th element is "value you are looking for"

return true

return false

## Binary search permalink

- Given a sorted array, divide and conquer by systematically eliminating half of the remaining elements (phone book) in the search for the target element.

`if no items`

return false

if middle item is "value you are looking for"

return true

else if "value you are looking for" < middle item

search left half

else if "value you are looking for" > middle item

search right half

Big O notion (on the order of)

`O(n/2)`

: Order of n/2`O(log2n`

): order of log nThey are approximations

🤔 **How do the algorithms compare In terms of running time (slowest -> fastest)?**

`O(n2)`

bubble sort, selection sort, insertion sort`O(n log n)`

merge sort`O(n)`

linear search`O(log n)`

binary search`O(1)`

**🤔 And what's in the opposite end of Big O?**

`Ω`

Greek Omega letter used to describe the best cases (Ω of ...)`Ω(n2)`

selection sort`Ω(n log n)`

merge sort`Ω(n)`

bubble sort, insertion sort`Ω(log n)`

`Ω(1)`

linear search, binary search

## Custom types permalink

**🤔 What is a struct?** It's a container, inside which you can put multiple other data types.

`typedef struct`

{

string name;

string number;

}

person;

## Bubble sort permalink

- Swap adjacent pairs of elements if they are out of order, effectively bubbling larger elements to the right and smaller ones to the left.

`Repeat n-1 times (later changed to repeat until no swaps)`

for i from 0 to n-2

if i'th and i+1'th elements out of order

swap them

- Amounts to
`O(n2)`

## Selection sort permalink

- Find the smallest unsorted element in an array and swap it with the first unsorted element of that array.

`for i from 0 to n-1`

find smallest item between i'th item and last item

swap the smallest item with the i'th item

Amounts to `O(n2)`

## Merge sort permalink

- Split the full aray into subarrays, then merge those subarrays back together in the correct order.

`if only one item`

return

else

sort left half of items

sort right half of items

merge sorted halves

## θ Theta permalink

for describing algorithms where `O`

and`Ω`

values are the same

`θ(n2)`

selection sort`θ(n log n)`

merge sort`θ(n)`

`θ(log n)`

`θ(1)`

## Insertion sort permalink

- Proceed once through the array from left to right, shifting elements as necessary to insert each element into its correct place.

## Recursion permalink

A function calling itself.

Classic example is the factorial:

`fact(n) = n * fact(n-1)`

Every factorial has two cases:

- base case: when triggered, will terminate the recursive process
- recursive case: which is where recursion actually occurs

`int fact(int n)`

{

if (n == 1)

return 1;

else

// With single line returns, you can take the curly braces away.

return n * fact(n-1)'

}