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.
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
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.
depends on what you think shrink means. If you mean decreasing, that's false even eventually.
[dead]
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 _____"
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
yes, GP is slightly off, but the idea of <= and < is accurate.
O(n) is: "there exists a K such that, for sufficiently large n, K*n is always larger".
o(n) is: "for every K, for sufficiently large n, K*n is always larger". (So o(2n+1) and o(2n) and o(n) are the same thing.)
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.
Ah, true, I was being sloppy. Thanks
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
I do hope you can find and reattach your ass; that does sound painful.
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...
ty, fixed. (ahh, copy paste.)