Confusing/Wrong explanation of bigO notatiion

[noinia]

I just came across the optimization handbook, and one of the first sentences I then read is:

"\mathcal{O}(n\log{}n) to mean the minimum bound time complexity of an algorithm is n\log{}n"

in the how to use section (1.1).

This sentence is either simply wrong, or at best very confusing, and therefore does not inspire great confidence in the rest of the book. I would suggest to rephase it to s.t. like

• .... , and
• big-O notation to indicate asymptotic running times of algorithms. In particular, if an algorithm takes O( n log n) time, then it can process any set of n input items in at most c*n log n time, for some fixed constant c.

Note in particular that this thus means that the maximum time, over all inputs of size n, is at most c*n log n (not the minimum). Nor does the bigO notation actually guarantee that this statement is best possible; i.e. if f(n) = O(n log n) then we also have f(n) = O(n^2). (I guess you somehow want to exclude that using 'minimum', but that simply makes the statement confusing). Finally note that the constant 'c' is actually important in the above statement. Having f(n) = O(n log n) simply does not mean that f(n) <= nlog n as the original sentence claims.

If we are being very precise, one should even add a "set of n, with n >= n_0, input items ........... for some fixed constants n_0 and c" in the above statement.

(by the way; having said all of that: I am still looking forward to reading about some of the nitty-gritty optimization details that I don't know about yet. So I do think this is a great project :D )

[doyougnu]

Ah great, yes this is very wrong indeed! Thanks for opening the ticket. If you have time would you like to contribute this fix? If not I can add the relevant text, I just wanted to make sure you get proper attribution.

[doyougnu]

Closing, issued a fix and follow up is #71