Best, average, and worst case describe one algorithm running on different inputs. Worst case is the slowest an input can make it. Best case is the luckiest input. Average case is what you expect over typical data.
Take searching an unsorted list for a value. Best case, it sits first, so O(1). Worst case, it sits last or is missing, so O(n). Average case lands around the middle, still O(n).
You usually plan around worst case because no input can make the algorithm run slower than that. Best case is often useless for guarantees. Average case matters when you know the data behaves normally and rare slow inputs are acceptable in your system.
Rewriting in plainer words…
This answer doesn't lend itself to a diagram - it reads best . No credits were charged.
Saved in this browser - sign in to keep your review list.
How should your speech become text?
Listening… your words appear above as you speak - tap Stop when you're done.
Recording · cr - tap Stop & transcribe when you're done.
Transcribing with AI…
Voice:
Keep going - a few more words and AI can grade it.
Interview lens
How interviewers actually use this question
Likely follow-ups
Quicksort's worst case is O(n^2). Why is it still a common default sort?Average is O(n log n). Random or median-of-three pivots make O(n^2) rare, and a fallback sort can cap the worst case.
Is best case the same thing as Big-Omega, and worst case the same as Big-O?No. A case picks which input you run, and O, Omega and Theta bound a growth rate. Linear search's worst case is Theta(n).
Best, average, and worst case all describe the same algorithm, just running on different inputs of the same size.
Worst case is the slowest any input can make it, best case is the luckiest input, and average case is what you expect over typical data.
Take searching an unsorted list for a value. If it sits first, that's O(1), and if it sits last or isn't there, that's O(n).
On average the value lands somewhere around the middle, so the average case is still O(n).
I plan around worst case, because no input can make the algorithm slower than that. Best case tells you almost nothing you can rely on.
Average case is the right number when you know your data behaves normally and your system can live with the occasional slow input.
Weak answers to avoid
Treats best case as Big-Omega and worst case as Big-OA case picks the input, and O, Omega and Theta bound a function. Show you keep them apart by saying linear search's worst case is Theta(n).
Sells the algorithm on its best caseBest case guarantees nothing, because a lucky input won't show up under real load. Lead with worst case, then say when average case is good enough.
Gives an average case without saying average over whatAn average needs an assumption about which inputs show up. Name it, for example random data, or the number means little.
Calls average-case linear search O(n/2)Big-O drops constants, so n/2 checks is still O(n). Average and worst case can grow at the same rate and differ only by a constant.
Interview lens
Likely follow-ups, what you can say, and the weak answers to avoid.
