Hacker News Reader

Comment by ddtaylor | Hacker News Reader

I think the notation is supposed to mean the worst performance. This is more an argument about amortized time analysis.

View on HN

No, this is a common misconception. Big O notation just represents a class of functions, it has nothing to do with complexity analysis, except for being very popular in the field. Whether an algorithm has O(N) worse case runtime or O(N) best case runtime or O(N) typical case runtime are all valid questions.

The misconception is mixing up notations. Using Big-O for the upper bound has been the norm for describing algorithms for at least half a century.

In Knuth's description[1] of Big-O notation (and related variants), from 1976, he starts out by saying:

    Most of us have gotten accustomed to the idea of using the notation O(f(n)) to stand for any function whose magnitude is upper-bounded by a constant times f(n) , for all large n .

Emphasis on upper-bounded. He goes on to describing other notations: Big-omega, for a lower bound, and so forth.

[1]:https://danluu.com/knuth-big-o.pdf

Yes O(f(n)) shows how the function f(n) is upper-bounded, but the point of the comment you're replying to is that the function f could be the worst-case, average-case, or best-case running time of an algorithm, or even a (say) number-theoretic function that has nothing to do with running times. (More here: https://stackoverflow.com/a/1960493 including the example in the comments of an algorithm whose best-case cost is O(n^2) and worst-case cost is Ω(n^3) — it is perfectly meaningful to give an upper bound on the best case, and a lower bound on the worst case.)

This is technically correct I'm sure but people usually use it w.r.t. f being simply the runtime of the function, in which case the common usage converges. I think the original comment may have a point here as I'm not sure the article necessarily caveated those definitions.

I don't think this is entirely true. I'd bet if you asked people the complexity of quiskort, they'd be more likely to remember it as O(n log n) than as O(n²), even though the first one is average case complexity and the second is worse case. Similarly, if you ask about hashtables or hash maps, you're more likely to hear O(1) than O(n), despite O(n) being the worse case complexity (when all items happen to have the same hash).

Instead, what I think happens is that people tend to talk about the average case complexity of well known algorithms, except that for most algorithms that's the same as worse case, so they tend to forget the distinction. And, if they're evaluating the complexity of something they wrote, they'll probably do the worse case analysis, since that's easier than the average case.

I'm not sure about this - for quicksort the usual answer for myself is o(nlogn) average case and o(n^2) worst, and for hash maps it's o(1) amortized complexity. Conversely for merge sort it's simply o(nlogn) flat.

These are well known cases precisely because when taught those runtime statements are caveated. I'd expect any discussion of runtimes on another topic to extend the same basic courtesy if the worst case didn't align.

Again, the worse case complexity can be O(N), but it can also be Big-Omega(N^2). Note that Knuth talks about the magnitude of a function, not of the runtime of an algorithm. The worse case complexity of an algorithm is a function, call it f_worse. The best case complexity of that same algorithm is a different function, call it f_best. It's just as meaningful to talk about O(f_worse) as it is to talk of O(f_best).

This is actually pretty common in CS. For example, people will often say that the typical case complexity of Quicksort is O(N log N), even though the worse case complexity is O(N^2). I doubt you'll find anyone who can tell you off the top of their head what is the actual complexity function of quicksort, and that will depend anyway on details of how the exact algorithm is implemented, even in pseudocode (will it do N reads, or 2N reads?).

Let's take a simple example: linear search. The worse case complexity is that we need to read every element from the array, and then compare it to the desired value, and we never find the desired value. So, in the worse case, the runtime is 2N (N reads + N comparisons) - f_worse(n) = 2n. In the best case, we read the first item in the array, we compare it to the pivot, and it is equal - so we need 2 operations - f_best(n) = 2. Now, we can say that O(f_worse(n)) = O(2n) = O(n). And we can also say that O(f_best(n)) = O(2) = O(1). So the best case complexity for linear search is O(1), and the worse case complexity is O(n). We never want to remember details like this to say things like "the best case complexity of linear search is 2".

Reply on news.ycombinator.com