Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
The 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 at 20:00
2  
@DanielFischer, make that into an answer. –  vonbrand Jan 30 at 20:00

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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 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 at 20:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.