Big O—Popular Algorithms

Sorting Algorithms

Table below shows the average time complexities for different sorting algorithms. Also, it includes corresponding (worst) space complexities.

Algorithm	Average Time	Worst Space
Quick Sort	$O(n \log{n})$	$O(\log{n})$
Merge Sort	$O(n \log{n})$	$O(n)$
Tim Sort	$O(n \log{n})$	$O(n)$
Heap Sort	$O(n \log{n})$	$O(1)$
Bubble Sort	$O(n^2)$	$O(1)$
Insertion Sort	$O(n^2))$	$O(1)$
Selection Sort	$O(n^2)$	$O(1)$
Tree Sort	$O(n \log{n})$	$O(n)$
Radix Sort	$O(nk)$	$O(n + k)$
Counting Sort	$O(n + k)$	$O(k)$

***More will be added.

Searching Algorithms

Table below shows the average time complexities for different sorting algorithms. Also, it includes corresponding (worst) space complexities.

Algorithm	Average Time	Worst Space
Binary search	$O(\log{n})$	$O(n)$
Linear search	$O(n)$	$O(n)$
Graph BFS	$O(v + e)$	$O(v)$
Graph DFS	$O(v + e)$	$O(v)$
Shortest-path (using min-heap)	$O(e + v \log{v})$	$O(v)$

***More will be added.

Other Algorithms

Will be updated. Check back later.