# CS50 Week 3: Algorithms

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

• 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 truereturn false``
• 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 falseif middle item is "value you are looking for"  return trueelse if "value you are looking for" < middle item  search left halfelse 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 n

• They 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

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

``typedef struct{  string name;  string number;}person;``

• 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)`

• 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)`

• Split the full aray into subarrays, then merge those subarrays back together in the correct order.
``if only one item  returnelse  sort left half of items  sort right half of items  merge sorted halves``

for describing algorithms where `O` and`Ω` values are the same

• `θ(n2)` selection sort
• `θ(n log n)` merge sort
• `θ(n)`
• `θ(log n)`
• `θ(1)`

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

• Classic example is the factorial: `fact(n) = n * fact(n-1)`
``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)'}``