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.

▲ ComplexSystems an hour ago | parent | next [-]

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.

▲ onionisafruit an hour ago | parent | prev | next [-]

For those of us uninformed, what’s the difference between O and o?

▲ bobmarleybiceps an hour ago | parent | next [-]

Knuth originally defining them https://dl.acm.org/doi/10.1145/1008328.1008329

▲ ruined an hour ago | parent | prev | next [-]

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

▲

jhanschoo an hour ago | parent [-]

Nitpick:

s/must shrink/must eventually shrink, after finitely many n/

Equivalently, must go to zero in the limit.

	▲	Davidzheng 12 minutes ago \| parent [-]
		depends on what you think shrink means. If you mean decreasing, that's false even eventually.

▲ theokrueger an hour ago | parent | prev | next [-]

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 _____"

▲

bobmarleybiceps an hour ago | parent [-]

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

	▲	npinsker an hour ago \| parent [-]
		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, Kn is always larger". o(n) is: "for every K, for sufficiently large n, Kn is always larger". (So o(2n+1) and o(2n) and o(n) are the same thing.)

▲ boothby an hour ago | parent | prev | next [-]

If f is O(g) and o(h) then

  Lim f/g -> C a constant

And

  Lim f/h -> 0

▲

adgjlsfhk1 44 minutes ago | parent | next [-]

> Lim f/g -> C a constant.

This isn't quite correct. O(g) doesn't require the limit to exist.

▲

appplication an hour ago | parent | prev [-]

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

	▲	boothby an hour ago \| parent [-]
		I do hope you can find and reattach your ass; that does sound painful.

▲ Ygg2 an hour ago | parent | prev [-]

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...

▲ craigcitro an hour ago | parent | prev [-]

ty, fixed. (ahh, copy paste.)