f(n) = o(g(n)) means as n increases, f(n)/g(n) must shrink
s/must shrink/must eventually shrink, after finitely many n/
Equivalently, must go to zero in the limit.
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 _____"
Big O is sort of like <=. little o is sort of like <.
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.)
Lim f/g -> C a constant
Lim f/h -> 0This isn't quite correct. O(g) doesn't require the limit to exist.
If you were joking then maybe you got me
https://stackoverflow.com/questions/1364444/difference-betwe...