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