Comparison of the complexity of algorithms

Comparison of the complexity of algorithms.

2.3.1 Algorithms

Algorithms — Note 4 of 6

Candidates need to know the best and worst case complexities for the searching and sorting algorithms. Candidates need to understand the difference between best, average and worst case complexity and why these can differ for an algorithm.

What you need to know

You need to compare the standard searching and sorting algorithms using Big O notation, including their best, average and worst cases, and explain why these can differ.

What to know

Linear search: best O(1), average and worst O(n). Binary search: best O(1), average and worst O(log n).
Bubble sort: best O(n) (already sorted, with a flag to stop when no swaps are made), average and worst O(n²).
Insertion sort: best O(n) (already sorted), average and worst O(n²).
Merge sort: O(n log n) in every case, but needs O(n) extra space.
Quick sort: best and average O(n log n), worst O(n²) (when the pivot is repeatedly the smallest or largest item).
Binary search tree search: average O(log n), worst O(n) if the tree is unbalanced.

Key terms

Best case: The input that makes the algorithm do the least work, e.g. the item being searched for is first in the list.
Worst case: The input that makes the algorithm do the most work, e.g. the item is last or not present.
Average case: The expected work over typical inputs.

Exam technique

Tip:Worst-case complexity is usually the most important when guaranteeing performance.

Code examples

Summary of time complexities

text

Algorithm        Best         Average      Worst        Extra space
Linear search    O(1)         O(n)         O(n)         O(1)
Binary search    O(1)         O(log n)     O(log n)     O(1)
Bubble sort      O(n)         O(n^2)       O(n^2)       O(1)
Insertion sort   O(n)         O(n^2)       O(n^2)       O(1)
Merge sort       O(n log n)   O(n log n)   O(n log n)   O(n)
Quick sort       O(n log n)   O(n log n)   O(n^2)       O(log n)