4 ms·
Nothing about big-O is specific to worst case. You can calculate a big-O for best case, average case, or worst case. For example, quicksort is O(n log n) best
by Calavar 3y ago
Nothing about big-O is specific to worst case. You can calculate a big-O for best case, average case, or worst case. For example, quicksort is O(n log n) best case, O(n log n) average case, and O(n^2) worst case. You may be confusing worst-case with upper bound: big-O is an asymptotic upper bound notation, but that refers to how we simplify the terms of the cost function and is entirely orthogonal to best/average/worst case.
- Xcelerate 3y ago> Nothing about big-O is specific to worst case Perhaps technically true but if someone asks you for the time complexity of an algorithm in an interview are you going to say “O(n)” without mentioning you’re referring to average-case? As far as I’m aware, without additional specifiers or context, people are referring to worst-case by default.
- Calavar 3y agoI'd say it's the opposite. I've never heard quicksort referred to as a O(n^2) algorithm for example, always as an O(n log n) algorithm with O(n^2) worst-case. Maybe in an interview you would explicitly say average-case, but I think that's more to show the interviewers that you realize that a single algorithm can have multiple big-Os.