Best Average Worst Case Complexity | Java Fresher Interview

These three describe how an algorithm behaves on different kinds of input. The best case is the luckiest input, where the algorithm does the fewest operations. The worst case is the most adversarial input, where it does the most. The average case is the expected cost over typical, realistic inputs. A clean example is linear search. In the best case the element I'm looking for is the very first one, so it's O of one. In the worst case the element is last, or not present at all, so I scan everything, which is O of n. The average case, if the element is somewhere in the middle, is about n over two, which is still O of n. When I give a Big-O in an interview, I default to the worst case, because that's the guarantee that holds no matter what input shows up, and in production I have to survive the bad day, not just the lucky one. But the average case genuinely matters too. The best example is quicksort. On average it's O of n log n, but its worst case is O of n squared, which happens on already-sorted input if you pick a naive pivot. We still use quicksort everywhere because that worst case is rare with good pivot selection and its constant factors are small. So my point is that quoting only the best case is misleading, and understanding all three is what tells me whether an algorithm is safe or risky for a given workload.