lkm543
commented
1 year ago Since O-notation describes an upper bound, when we use it to bound the worst case running time of an algorithm, we have a bound on the running time of the algorithm on every input—the blanket statement we discussed earlier. Technically, it is an abuse to say that the running time of insertion sort is O.n2/, since for a given n, the actual running time varies, depending on the particular input of size n. When we say “the running time is O.n2/,” we mean that there is a function f .n/ that is O.n2/ such that for any value of n, no matter what particular input of size n is chosen, the running time on that input is bounded from above by the value f .n/. Equivalently, we mean that the worst-case running time is O.n2/.
Big-O describes an upper bound; therefore, it is useful for measuring the efficiency of an algorithm in the worst-case scenario. However, if we would like to describe an upper bound of the average case, it meant that the we would like to know the average of all possible inputs. The worst case of average of all possible inputs of quick sort was O (N log N).
Ref: Introduction to algorithms-3rd Edition
In the book, Big O is described as worst case. Is such association ideal?
I think BigO from maths point of view is just about limiting behavior or upper bound.
In fact, we often say worst case time complexity for quick sort is O(N^2) while average time complexity for quick sort is O (N log N)