Data Structures and Algorithms - Time Complexities

Sorting Algorithm	Best Case	Average Case	Worst Case
Bubble Sort	$O(n^2)$	$O(n^2)$	$O(n^2)$
Insertion Sort	$O(n)$	$O(n^2)$	$O(n^2)$
Selection Sort	$O(n^2)$	$O(n^2)$	$O(n^2)$
Quick Sort	$O(n\log{n})$	$O(n\log{n})$	$O(n^2)$
Merge Sort	$O(n\log{n})$	$O(n\log{n})$	$O(n\log{n})$

The resonse behind each time compexities

Bubble Sort & Selection Sort

For the first run we go through all the n elements For second run we go through n-1 elements For nth run we go through 1 element

So total runs = $n + (n-1) + ... + 1$ $= \frac{n(n+1)}{2}$ $= \frac{n^2}{2} + \frac{n}{2}$

Now for time complexity calculation we only focus on the highest degree and we ignore the coefficients. So the time complexity stands here $O(n^2)$

This is for best case average case and worst case.

Insertion sort - best case

For average and worst case the calculation is same as bubble and selection sort

But for best case, we only check 1 element in the internal loop every time (which is for already sorted array)

Hence the complexity becomes $O(n*1) = O(n)$

Quick Sort and Merge sort

In all cases of merge sort and in Best and average case of quicksort we divide the array in two halves each time. And in each layer of the tree of division we go through n elements.

Now the height of a tree is $\log{n}$

So the merge of n elements goes $\log{n}$ times

So the time complexity stands $O(n \log{n})$

Quick Sort worst case

In worst case of Quick Sort the time complexity becomes $O(n^2)$ beacuse if we select the worst pivot every time we first time go through n elements then n-1 elements and finally reach 1, which makes the total runs as -

$n + (n-1) + ... + 1$ $= \frac{n(n+1)}{2}$ $= \frac{n^2}{2} + \frac{n}{2}$

So the time complexity stands here $O(n^2)$