Note in this case the title says "O(n log n)", but the important part is this is "o(n log n)", not just "O(n log n)'. The former is a strict subset of the latter. We already knew how to multiply two n-bit integers in O(n log n) time, via the FFT.
Roughly speaking, O(n log n) means "grows no faster than k(n log n) for some k", whereas o(n log n) means grows strictly more slowly* than k(n log n) for all* choices of k.
yeah you're right. I wrote that poorly and seems I can't edit it now..
In the link I shared, he does propose the similar theta and omega notations and provides the existing definition for big O.
Hmm you're right it's no more rigorous what I said. (For each positive number the expression must eventually, after finitely many terms, always be smaller than that number thereafter)
But you're not right in that the upper bound of that expression eventually stops decreasing, in fact for simple f and g as long as f is positive and eventually bounded by g the expression will decrease infinitely often if my intuition is correct
To complement on other comments that have already provided definitions.
The big O notation is very often used to denote exact complexity of an algorithm even if the notation is technically an upper bound.
The little o notation is usually used to denote a small asymptotic improvement over some known complexity.
For example if some sublinear algorithm would have n^(7/8) complexity - would be probably advertised as big O of that.
But n^(1-eps) is shared as o(n) with exact constant provided as a detail.
Both define upper boundary, but big O can read like "the function is generally proportional to ___" and little o can read like "the function is never more than _____"
> "there exists a K such that, for sufficiently large n, K*n is always larger".
For what it's worth you can leave out the 'sufficiently large n' part, assuming we're talking about positive integers (or continuous functions on the nonnegative reals). I like to leave it in though because it makes the jump to defining both o, O and Theta in terms of lim sup f/g a little easier.
I don't think any of those are right. The latter two are trivially equivalent, the former also is since it differs by a factor of at most 3 for all n >= 1.
I still think the simplest definition for o(f) is 'g in o(g) iff O(g) is a proper subset of O(f)'. Or you can just say g is dominated by f in the sense that lim sup g/f = 0.
I'm fairly sure those two are equivalent, but it's a good little exercise.