3 ms·

In lwn comments a guy insists that “O(f(n)) is by definition a bound over the worst-case case input to a function.” Is that actually true? Mathematically: O(f

In lwn comments a guy insists that “O(f(n)) is by definition a bound over the worst-case case input to a function.” Is that actually true? Mathematically: O(f(n)) is asymptotic bound when n approaches infinity, which could be used to describe worst, best, average and other cases. Have programmers redefined O to specifically mean worst case?

lkirkwood 2y ago
No, I believe you are forgetting the context. Big O is a upper bound on the growth rate of a function. In this case the function describes the time taken, therefore a higher time is a "worse case". So Big O is, in this scenario, a bound on the worst case time taken (essentially what the commenter said). Certainly as I understand it your definition of Big O is incorrect - it provides exclusively an upper bound. Big Omega is used for a lower bound and Big Theta for an upper and lower bound.
- stoperaticless 2y ago
  Math definition goes something like this: f(n)=O(g(n)), if exists C such that f(n) < C x g(n), when n goes to infinity. Function “quickSortExecutionTime(permutation)” depends on exact input (each permutation/shuffle has different exec time), parameter “permutation” can not go to infinity, so it can’t be used with O(n) directly. (Parameter need to be single real number) QuickSortWorstCaseTime(n) is single valued function thus, it can be used with O(n) notation. Same is true for quickSortAvgCaseTime(n) and quickSortBestCaseTime(n). But you answered my question. (Very indirect “Yes” :) )
  - lkirkwood 2y ago
    It's true that in the case of a sorting algorithm it's not immediately obvious how to analyse the time complexity with Big O. However, I feel that you may be getting bogged down in semantics. Perhaps it is accurate to say that when Big O is used to describe the time complexity of a function in computer science the variable n in O(f(n)) usually describes the size of the input, which may not be common knowledge. But if the question is: > Have programmers redefined O to specifically mean worst case? Then in general I would say no. I suppose to answer more concretely I would have to ask: "Which programmers?"
John23832 2y ago
Big O is upper bound (worst case), big theta is average case, big omega is lower bound (best case).
- msm_ 2y ago
  Not according to my understanding of the subject, my copy of "Introduction to Algorithms", and Wikipedia. Big O is an upper bound for a function growth - being O(f(n)) means growing asymptotically slower than f(n) (up to a multiplication by a constant). Small o is a lower bound for a function growth - being o(f(n)) means growing asymptotically faster than f(n) (up to a multiplication by a constant). Big theta means the function grows exactly that fast - being Θ(f(n)) means the function is both O(f(n)) and o(f(n)), so being exactly f(n) up to a multiplication by a constant. In practice, due to typographical limitations, people use O(n) where Θ(n) would be more precise. Average case, best case, worst case, amortized etc complexities are a wholly different thing. For example, quick sort is Θ(n^2) worst case and Θ(n log n) average case.

lkirkwood 2y ago

No, I believe you are forgetting the context. Big O is a upper bound on the growth rate of a function. In this case the function describes the time taken, therefore a higher time is a "worse case". So Big O is, in this scenario, a bound on the worst case time taken (essentially what the commenter said). Certainly as I understand it your definition of Big O is incorrect - it provides exclusively an upper bound. Big Omega is used for a lower bound and Big Theta for an upper and lower bound.

stoperaticless 2y ago
Math definition goes something like this: f(n)=O(g(n)), if exists C such that f(n) < C x g(n), when n goes to infinity. Function “quickSortExecutionTime(permutation)” depends on exact input (each permutation/shuffle has different exec time), parameter “permutation” can not go to infinity, so it can’t be used with O(n) directly. (Parameter need to be single real number) QuickSortWorstCaseTime(n) is single valued function thus, it can be used with O(n) notation. Same is true for quickSortAvgCaseTime(n) and quickSortBestCaseTime(n). But you answered my question. (Very indirect “Yes” :) )
- lkirkwood 2y ago
  It's true that in the case of a sorting algorithm it's not immediately obvious how to analyse the time complexity with Big O. However, I feel that you may be getting bogged down in semantics. Perhaps it is accurate to say that when Big O is used to describe the time complexity of a function in computer science the variable n in O(f(n)) usually describes the size of the input, which may not be common knowledge. But if the question is: > Have programmers redefined O to specifically mean worst case? Then in general I would say no. I suppose to answer more concretely I would have to ask: "Which programmers?"

John23832 2y ago

Big O is upper bound (worst case), big theta is average case, big omega is lower bound (best case).

msm_ 2y ago
Not according to my understanding of the subject, my copy of "Introduction to Algorithms", and Wikipedia. Big O is an upper bound for a function growth - being O(f(n)) means growing asymptotically slower than f(n) (up to a multiplication by a constant). Small o is a lower bound for a function growth - being o(f(n)) means growing asymptotically faster than f(n) (up to a multiplication by a constant). Big theta means the function grows exactly that fast - being Θ(f(n)) means the function is both O(f(n)) and o(f(n)), so being exactly f(n) up to a multiplication by a constant. In practice, due to typographical limitations, people use O(n) where Θ(n) would be more precise. Average case, best case, worst case, amortized etc complexities are a wholly different thing. For example, quick sort is Θ(n^2) worst case and Θ(n log n) average case.