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
Lim f/g -> C a constant
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.
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...
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...