Hacker News Reader

Comment by opportune | Hacker News Reader

NO. BIG O notation is not average unless specified as such! It is an equivalence class of the provable upper bound on the execution time of the algorithm on an arbitrary input. There are algorithms like quick sort where average runtime != “big O of quicksort”

View on HN

This is completely wrong. Big O has nothing to do with algorithms. Big O notation can be used for any mathematical function from an ordered set to another ordered set, including average runtime of an algorithm as a function of data size, worst-case runtime of an algorithm as a function of data size, guaranteed amortized runtime of an algorithm as a function of data size, or anything else (including things with nothing to do with computation -- it's perfectly reasonable to say things like x^2 + 5x + 2 is O(x^2) and just be talking about pure math with no reference to algorithms).

If someone asked "what is the runtime of quicksort in big O terms", it is ambiguous whether the answer is O(n^2) or O(n*log(n)) , since it's not clear which function you're talking about.

To be honest, this is false too. You need functions with values that can be multiplied by scalars. If you just have ordered set, then you can't account for this constant from the definition. Alternatively, you could say that values of the function need to be from a normed vector space (but I'm not sure if it can be extended furthermore. Maybe normed C-module?)

Sure, but that doesn't change my point.

Sure that's what it is formally, but that's not the applied meaning the article is about. Take an hypothetical search algorithm that is O(1) except when the container you're searching is of length 50, then it's O(n). That makes the algorithm O(n), right?

(yes this is a stupid contrived example, and I know one can make any case when one can make up any reality etc. - but I think it's a valid style figure in this case, to contrast the theoretical definition with the application).

Would you toss out that search algorithm and say 'well we have algorithms that search in better than O(n) so forget about this one'? No, you'd do 'if (container.size() == 50) { return container.bisect_find(key); } else { container.lalaland_find(key); } And that's exactly the difference between the theoretical concept and the application.

(although I'll admit that I started out writing the comment trying really hard to avoid the word 'average' because it's so confusing and then it still slipped in)

No, that algorithm is O(1).

50 is a constant. As n -> infinity, the algorithm runs in constant time.

Specifically, I can pick some number C such that C * f(n) > the number of operations, then the algorithm is O(f(n)).

So I choose f(n) == 1, and C == 100.

Then the runtime of the algorithm is 1,1,1,1,1...., 50,1,1,1,1,.... For all values of n, this is less than C * f(n) == 100, a constant, so it is O(f(n)). f(n) is 1, so it is O(1).

Yes you're right - let me modify my contrived example and say 'at exactly midnight, the complexity is O(n)'.

(the cool part about contrived examples is that you can keep making things up until it fits - now I'm just hoping I didn't miss something again like the first time :) )

Still doesn't work. Waiting one minute is constant time. (to be clear, I'm going to be able to come up with a counterexample for anything you throw at me because you're assumption here is just false, in general an algorithm that is O(f) for all values except n is O(f), because you can pick a constant greater than n, no matter what the dimension n acts in is).

(If you reject that and claim that just because I can construct an algorithm that is O(1) from yours doesn't mean that your algorithm is O(1), I'll point out what you presented isn't technically a function, since its not mathematically pure, so the concept of Big-O is ill-formed)

Well but (I think) what you're talking about now is the complexity of the 'wrapper' function I posed, not the complexity of the hypothetical algorithm I started out with. Yes you can add an indirection that converts it back into O(1) but the original, but that wasn't the point. I think. But then again, maybe what your second paragraph is saying is exactly that? I'll admit that I lost track of things somewhere between writing my original comment, switching back and forth to my code between compiles and now being back here :)

Also, I don't understand what you mean by 'mathematically pure', but that's on my end.

The Big O of an algorithm does not change based on data size. Even if your set had precisely 1 record in it - the code you write, if it loops over every item in the set (even if it's only one item) - is still O(n).

Yes I know that - was this reply meant for another comment?

So there's two ways of looking at it, the more handwavy is "my construction that treats your algorithm as a black box does only ever strictly more work than your algorithm. If mine runs in a constant number of operations, yours must as well." And certainly your algorithm runs in amortized constant time (which is a weird phrase).

The other way is to ask "what is a function"?

Normally, a sorting function is expressed as

    sort(List[Comparable]) -> List[Comparable]

your sorting function however has a different way of working. It has an additional input, the time. Now you might argue that you aren't taking the time as input, but you are...somehow. So in reality, your function has a signature

    sort(int, List[Comparable]) -> List[Comparable]

There's this extra int input which is weird, so you don't have. Computational complexity tools like O-notation don't concern themselves with such things. O notation only cares about how the runtime changes as the size of the input changes.

If the size of the int "time" is bounded (which it is, since the max is 86400), then one of the inputs is constant. It can be ignored.

Purity in this context is the idea that the function only acts on its inputs, there are no external forces that modify how it works. Pure functions are mathematical objects, impure functions aren't really.

So once you convert your construction to being pure, it becomes more clear why the function is ill-formed: you've got this extra constant size input (that runtime analysis can ignore) that you claim affects the runtime. Something is clearly amiss.

No, it's best-case O(1), worst-case O(n) (technically O(1) since there is a constant upper-bound, but let's pretend you said it's O(n) when length is divisible by 50 instead of equal to 50) and average-case O(1).

Each of those functions has its own big O, without specifying which function you are talking about big O isn't meaningful.

Reply on news.ycombinator.com