Comment by flebron
1 day ago
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.
For those of us uninformed, what’s the difference between O and o?
Knuth originally defining them https://dl.acm.org/doi/10.1145/1008328.1008329
That sounds like Knuth came up with them, but the notation is much older than 1976
2 replies →
Best explanation of big-O I've read, in a single opening sentence, no less!
That doesn't define little-o at all?
In fact, he refers to Landau for the definition of little-o.
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.
Pedantic correction: big O is more like <=, little o like strict <. Big theta, Θ, is like =. There's also omegas, big and small, for >= and >.
1 reply →
f(n) = O(g(n)) means as n increases, f(n)/g(n) must not grow beyond a constant
f(n) = o(g(n)) means as n increases, f(n)/g(n) must shrink
Nitpick:
s/must shrink/must eventually shrink, after finitely many n/
Equivalently, must go to zero in the limit.
3 replies →
Those are complexity classes. It makes more sense to use '∈' instead of abused '='.
If f is O(g) and o(h) then
And
> Lim f/g -> C a constant.
This isn't quite correct. O(g) doesn't require the limit to exist.
1 reply →
Lmao! If someone is asking the difference between big and little o notation this is absolutely not the right way to clarify it.
If you were joking then maybe you got me
1 reply →
Both are upper bounds. But small o is strictly smaller than upper bound. Big O is not greater than upper bound.
https://stackoverflow.com/questions/1364444/difference-betwe...
Big O basically drops constants
O(2n+1) = O(2n) = O(n)
o(2n+1) > o(2n) > o(n)
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 _____"
> o(2n+1) > o(2n) > o(n)
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.
that's not the convention I know... (from CLRS algorithms book).
Big O is sort of like <=. little o is sort of like <.
https://dl.acm.org/doi/10.1145/1008328.1008329
2 replies →
ty, fixed. (ahh, copy paste.)