Skip to interview prep
Apexed

65. What is the difference between best, average and worst case analysis, and how do they relate to O, Ω and Θ?

EasyAlgorithm analysis

Technical
Show model answer

The cases describe which inputs you are measuring: the cheapest input of size n, the expected cost under some input distribution, or the most expensive input. For quicksort with a naive pivot, the best and average cases are Θ(n log n) but the worst case (already sorted input) is Θ(n²).

O, Ω and Θ are bounds on a function and are independent of the case. You can say the worst case of insertion sort is Θ(n²) and the best case is Θ(n). Saying "insertion sort is O(n²)" is a true upper bound on every case; saying it is Ω(n) is a true lower bound on every case. Average-case claims should always state the assumed distribution.

What is the difference between best, average and worst case analysis, and how do they relate to O, Ω and Θ — Data structures & algorithms interview question — A