Comment by tsimionescu | Hacker News Reader

Comment by tsimionescu | Hacker News Reader

Parent Full thread

> It is not redundant to say "average case O(n log(n))". It's not formally a correct usage of O().

You are wrong. It is perfectly formally correct to say "average case complexity is 2n log(100n) + 78n + 90, which is O(n log (n))".

> By definition, O(X) means that the maximum of the number of operations over all possible inputs of length n is at most X.

No, that is, in fact, a colloquial use of O(X). O(X), formally, is simply the set of all functions that are bigger than X up to some constant factor. It has nothing to do with number of operations in itself.

Instead, we formally define complexity functions for an algorithm, which are the minimum/average/maximum number of operations the algorithm will execute for any input of size N; call these functions Cmin(n), Cavg(n), Cmax(n). Then, we can say that C_(n) is in O(X(n)) (or, as a shorthand, C_(n) = O(X(n))) if there exists a number k such that C_(n) < k * X(n) for any n > n0.

So, we can say that the best case complexity of an algorithm, Cmin(n), is O(n^2); this means that even for the best possible input of length n, it will execute at least k * n^2 steps, for some k. Or, we can say that the worse case complexity of some algorithm, Cmax(n), is Omega(n^2); that is, that even in the worse case input of length n, it will execute less than k * n^2 steps, for some k.

In fact, the concept "number of steps that an algorithm will execute for any input of size n" is not a mathematical function at all (unlike min/max/avg number of steps), since there isn't, in general, a unique such number for any given size.

So, I would argue that saying "complexity O(n^2)" is in fact ill-defined formally, and that, if you want to be formal, you must specify "worst case complexity O(n^2)".

I think you're right on the formalism, and I shouldn't have brought that in. I've been out of grad school a while and should clearly brush up on my theory.

My main line of reasoning is:

1. If I say "this algorithm time-complexity is O(X)", I mean that all possible cases are in O(X).

2. If all possible cases are in O(X), then the worst case is in O(X).

3. If the worst case is in O(X), then any other case will also be in O(X). This follows from our definition of "worst case".

4. Therefore, "all possible cases are in O(X)" <=> "worst case is in O(X)"

5. Therefore, "this algorithm time-complexity is O(X)" <=> "this algorithm time-complexity is worst-case O(X)"

If your thought is that 1) isn't a formal definition, fair enough. It may have been a convention we adopted within the department. But aside from that, I think the reasoning is solid.

Would argue it isn't perfectly formally correct, because "average case complexity" isn't well defined. Is average here mean, median or mode? It is typically used as if it meant, 90th percentile, or all but a few degenerate cases.

But that is a bit nit picky.

I'm not sure I've ever seen anyone argue over which measure of central tendency to use to assess the "average case". You certainly could, but it doesn't strike me as a particularly productive argument; in common parlance, an average is essentially always either an arithmetic mean or a non-rigorous informal typical case unless otherwise specified; it also normally doesn't matter very much since most algorithms of interest do have their complexity distributed across inputs s.t. as input size goes to infinity one regime describes the behavior on almost all inputs. It's surprisingly hard to even come up with one without just having having an approximately constant fraction of inputs just be trivial cases.

The much more important problem with "average case" complexity, particularly infamously for sorts, is just that practical "typical" inputs aren't distributed evenly over the space of possible inputs; pathological inputs have, after all, practically by definition, a nontrivial almost–computable property that informally gives them more of a reason to exist than than the average input.

The claim was "perfectly formally correct". If the average is arithmetic mean of all possible inputs, then average case O is worst case O because the worst case term dominates. Therefore they are using an informal definition of average, which doesn't jive with formally correct.

> then average case O is worst case O because the worst case term dominates

No, you're overgeneralizing. It's true that the worst case term dominates if e.g. a constant fraction of inputs exhibit the worst-case behavior, so that average complexity is lower bounded by a constant fraction of the worst-case behavior.

This isn't true for the kind of algorithms where it's customary to talk about average case behavior. We only normally talk about average cases when as input size increases, the fraction of inputs with the higher complexity bound shrinks faster. For example, we can imagine an algorithm which, on inputs of size n, requires n^2 operations on 1/n of possible inputs, and n operations on the other (n-1)/n inputs. Then the average runtime is, formally, (n^2)*(1/n)+n*(n-1)/n=2n-1, which is still O(n), even though the worst-case runtime is still O(n^2).

Where this goes wrong is, e.g. perhaps the O(n^2) runtime occurs on "trivial" inputs which are disproportionately likely to appear. For example, if we the above hypothetical function is idempotent and runs in O(n^2) on all of its possible outputs, but O(n) on all other inputs, it'd be easy to accidentally quadratic by calling it on its result repeatedly under the assumption that it's safe to do so.*

Reply on news.ycombinator.com