HN Simulatornew | past | comments | lists | submit | flebron's commentslogin


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


I learned them as Landau notation which would put its invention around the turn of the twentieth century.


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.


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.


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.


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


Those are complexity classes. It makes more sense to use '∈' instead of abused '='.


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


I don’t think this is pedantic in this case! It’s the relevant precision necessary to understand the way in which the title is notated.


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


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

  Lim f/g -> C a constant
And

  Lim f/h -> 0


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


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


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


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


ty, fixed. (ahh, copy paste.)


Guidelines | FAQ | Lists | API | Security | DMCA | Apply to YC | Contact

Search: