Comment by contravariant

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