Big O can describe three different scenarios for the same algorithm. Understanding which one you're reporting is critical in interviews.
1. Best Case (Rarely Useful)
If you search for the number 5 in the array [5, 1, 2, 3], you find it on the first comparison. $O(1)$.
This is misleading as a design metric. You cannot guarantee the lucky scenario in production. Designing for best case is like planning a road trip assuming every traffic light will be green.
2. Average Case (The Reality)
On average, if you search for a random element in an unsorted array, you'll inspect half of it before finding it. $O(N/2)$, which simplifies to $O(N)$.
Average case is useful for probabilistic analysis and is what you'd report for randomized algorithms like Quick Sort (average $O(N \log N)$, worst $O(N^2)$).
3. Worst Case (The Guarantee — What Interviews Want)
What if the item is at the very end, or not in the array at all? You must search every element. $O(N)$.
Interviews almost always ask for worst case. In production systems, you need to know the upper bound on how bad things can get. An SLA guarantees response time in the worst case, not the average. A system that is usually fast but occasionally takes 10 minutes is broken.
The Three Greek Letters (For Completeness)
Formally, computer scientists use:
- Big O (O) — upper bound (worst case). Most common in interviews.
- Big Omega (Ω) — lower bound (best case).
- Big Theta (Θ) — tight bound (average case, when best and worst are the same order).
In practice, "Big O" is used colloquially to mean worst-case complexity, and that's the convention you should follow in interviews unless asked otherwise.