I'm just starting to learn big O notation and there's one thing in particular that bothers me. Say $f(n) = O(g(n)+c))$, where c is a constant. To my understanding, $f(n)$ can just be represented as $O(g(n))$ because constant terms don't really matter as n approaches infinity. However, are there functions where this is not necessarily true?
Asked
Active
Viewed 241 times
0
-
2The added constant matters if $g(n)$ becomes small for some large $n$, e.g. if $g(n) \to 0$ for $n\to\infty$. – Daniel Fischer Jan 30 '14 at 20:00
-
2@DanielFischer, make that into an answer. – vonbrand Jan 30 '14 at 20:00
1 Answers
3
The constant $c$ can be absorbed by $g(n)$ if there is a $\delta > 0$ and an $n_0$ such that $g(n) \geqslant \delta$ for all $n \geqslant n_0$. If that is not the case, the constant cannot be absorbed by $g(n)$. If you have $g(n) \to 0$ for $n \to \infty$, then the $g(n)$ part can be absorbed by the constant, but if $g$ takes large as well as small values for large $n$, for example
$$g(n) = n^{(-1)^n},$$
then neither can $g(n)$ absorb the constant $c$, nor can $c$ absorb $g(n)$.
Such a $g$ is however not something one usually has in big-Oh estimates. Usually, one uses functions that have a regular monotonic growth or decay to bound the values of the other function.
Daniel Fischer
- 206,697
-
I'm slightly confused by your two posts. In the first you said the added constant matters if $g(n) \to 0$ for $n \to \infty$. But in the second post, you said the $g(n)$ part can be absorbed by the constant. Am I just missing something really simple? – user3254763 Jan 30 '14 at 20:17
-
If $g(n) \to 0$, then the constant is the only thing that matters (I assume $c > 0$, if $c = 0$, then there is only $g(n)$ left), and then $g(n)$ can be absorbed by the dominating term [the constant]. – Daniel Fischer Jan 30 '14 at 20:25