# Complexities of basic operations of searching and sorting algorithms [closed]

Wiki has a good cheat sheet, but however it does not involve no. of comparisons or swaps. (though no. of swaps is usually decides its complexity). So I created the following. Is the following info is correct ? Please let me know if there is any error, I will correct it.

Insertion Sort:

• Average Case / Worst Case : $\Theta(n^2)$ ; happens when input is already sorted in descending order
• Best Case : $\Theta(n)$ ; when input is already sorted
• No. of comparisons : $\Theta(n^2)$ in worst case & $\Theta(n)$ in best case
• No. of swaps : $\Theta(n^2)$ in worst/average case & $0$ in Best case

Selection Sort:

• Average Case / Worst Case / Best Case: $\Theta(n^2)$
• No. of comparisons : $\Theta(n^2)$
• No. of swaps : $\Theta(n)$ in worst/average case & $0$ in best case At most the algorithm requires N swaps, once you swap an element into place, you never touch it again.

Merge Sort :

• Average Case / Worst Case / Best case : $\Theta(nlgn)$ ; doesn't matter at all whether the input is sorted or not
• No. of comparisons : $\Theta(n+m)$ in worst case & $\Theta(n)$ in best case ; assuming we are merging two array of size n & m where $n<m$
• No. of swaps : No swaps ! [but requires extra memory, not in-place sort]

Quick Sort:

• Worst Case : $\Theta(n^2)$ ; happens input is already sorted
• Best Case : $\Theta(nlogn)$ ; when pivot divides array in exactly half
• No. of comparisons : $\Theta(n^2)$ in worst case & $\Theta(nlogn)$ in best case
• No. of swaps : $\Theta(n^2)$ in worst case & $0$ in best case

Bubble Sort:

• Worst Case : $\Theta(n^2)$
• Best Case : $\Theta(n)$ ; on already sorted
• No. of comparisons : $\Theta(n^2)$ in worst case & best case
• No. of swaps : $\Theta(n^2)$ in worst case & $0$ in best case

Linear Search:

• Worst Case : $\Theta(n)$ ; search key not present or last element
• Best Case : $\Theta(1)$ ; first element
• No. of comparisons : $\Theta(n)$ in worst case & $1$ in best case

Binary Search:

• Worst case/Average case : $\Theta(logn)$
• Best Case : $\Theta(1)$ ; when key is middle element
• No. of comparisons : $\Theta(logn)$ in worst/average case & $1$ in best case

1. I have considered only basic searching & sorting algorithms.
2. It is assumed above that sorting algorithms produce output in ascending order
3. Sources : The awesome CLRS and this Wiki
– Raphael
Apr 3 '13 at 14:12
• This is not a question so is off-topic. Feb 8 '14 at 9:25
• I voted to close too. This is perhaps challenging to salvage too because the "question" is rather broad (what are the basic search and sorting algorithms, exactly?)
– Juho
Feb 8 '14 at 9:32

For general algorithm of bubble sort worst case comparisons are $\Theta(n^2)$ But for special case algorithm where in you add a flag to indicate that there has been a swap in previous pass. If there were no swaps then we come out of the loop since array is already sorted. In this case comparisons are $n$ not 0.
For Quick sort you have mentioned that worst case swaps are $n^2$. Well worst case scenario for quick sort is when all elements are in sorted order thus there won't be any swaps so it should be zero.
• I don't understand your answer. Detecting "no swaps" in bubble sort certainly makes it faster but, if the input is in the opposite order to the output, you still need $\Theta(n^2)$ swaps, even with "no swap" detection. Quicksort normally runs in time $O(n\log n)$ so the best case cannot be $n^2$ swaps. Feb 8 '14 at 9:32
• In the normal case, quicksort runs in time $O(n\log n)$. Therefore, the best case is also $O(n\log n)$ time steps (it might be faster but $O(-)$ gives only an upper bound). In $O(n\log n)$ steps, you cannot do anything $n^2$ times -- comparisons, swaps, or anything else. You can't use more than $O(n\log n)$ memory, either. The best case for any complexity measure at all cannot be more than $O(n\log n)$. Feb 8 '14 at 14:46