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


![Sorting_quicksort_anim.gif](https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif)

* [Implement with C](https://gist.github.com/erictt/daede65d8178a93a25a5e52ed07d69aa)
* [Implement with Python 3](https://gist.github.com/erictt/0438c9db11b3b25f0e24c212d8f3c3b9)

## Refers
* [CS50/week 3](http://docs.cs50.net/2016/fall/notes/3/week3.html)
* [Sorting_algorithm - Wikipedia](https://en.wikipedia.org/wiki/Sorting_algorithm)
* [Merge_sort - Wikipedia](https://en.wikipedia.org/wiki/Merge_sort)
* [Quicksort - Wikipedia](https://en.wikipedia.org/wiki/Quicksort)
* [Comparison Sorting Visualization](https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html)