6 ms·
It's little o notation. It does not depend on n. For example x^2 is in O(x^2) but is not in o(x^2).
by knuthsat 5y ago
It's little o notation. It does not depend on n.
For example x^2 is in O(x^2) but is not in o(x^2).
- dwohnitmok 5y agoWhen used in that equation it's meant to implicitly depend on n as edflsafoiewq points out. o(1) stands for o(f(n)) where f(n) = 1. Hence any function g(x) in the family of functions represented by o(1) must be less than c * f(x) for every positive c and all x greater than some m. This is exactly the statement that any function in the family of functions o(1) must tend to zero. Whenever you see big-O/little-O/theta notation there is always an implied dependent variable, even for o(1)/O(1)/Theta(1).
- omegalulw 5y agoI think a nuance people are missing is that for big O, it is sufficient for the existence of any positive C and x, but for small o there must always exist an x for every c.