# Week 3

## Computational Complexity

• worst-case scenario: $O$
• best-case scenario: $\Omega$
• theta, $\Theta$, if the running time of an algorithm is the same in the worst-case ($\Omega$) and the best-case ($O$).
• We don’t actually care about how complex the algorithm is precisely, only it’s tendency, which dictated by the highest-order term.
• for example, $n^3$, $n^3+n^2$, $n^3-8n^2+20n$. when n is 1,000,000, the values will be $1.0*10^{18}$, $1.000001*10^{18}$ and $9.99992*10^{17}$. The lower terms became really irrelevant. So we only take the highest-order term, which is $n^3$ here.

### Common Classes

• from fast to slow:
• $O(1)$ constant time
• $O(\log{n})$ logarithmic time
• binary search
• $O(n)$ linear time
• linear search
• $O(n\log{n})$ linearithmic time
• merge sort
• $O(n^2)$ quadratic time
• bubble sort, selection sort, insert sort
• $O(n^c)$ polynomial time
• $O(c^n)$ exponential time
• $O(n!)$ factorial time
• $O(\infty)$ infinite time
• $O(1)
• More comparisons: https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

for i from 0 to n-1
find smallest element between i’th and n-1’th
swap smallest with i’th element

repeat until no swaps
for i from 0 to n-2
if i’th and i+1’th elements out of order
swap them

for i from 1 to n-1
call 0’th through i-1’th elements the “sorted side”
remove i’th element
insert it into the sorted side in order

on input of n elements
if n < 2
return
else
sort left half of elements
sort right half of elements
merge sorted halves

pick an element called a pivot from array
partition the array with pivot
if element i > pivot
move to right
in the end swap the pivot to middle()
recursively apply steps before to the left and the right sub-array without pivot