# Can I simplify log(n+1) before showing that it is in O(log n)?

Had a question about the following:

$$\log (n+1) \in O(\log n)$$

Can the left side be simplified any further or do I need to just go ahead and find a c and n that hold?

• Just go ahead. By the way, $log(n^2)$ is also $O(log n)$. Mar 8, 2016 at 19:37
• I don't understand the question. What do you mean by "simplify"? When are you ever allowed to change the left side?
– Raphael
Mar 8, 2016 at 19:39
• @Raphael I assume "simplify" in the sense of manipulating the expression $\log(n+1)$ to get something simpler. (E.g., $(x+1)^2-(x-1)^2$ simplifies to $4x$.) Mar 8, 2016 at 22:34
• Or it might be a more involved view of "simplification" that applies specifically to considerations of Big-O. For example, you might say that if $g(x)$ is $O(f(x))$, then $f(x) + g(x)$ "simplifies" to $f(x)$ in this context, and so $x^2 + x$ simplifies to $x^2$. Of course you have to be careful to apply correctly the theorems that have given you such "simplification rules". Mar 9, 2016 at 1:00

## 4 Answers

Simplifying the left-hand side is a good strategy. You aren't going to find a simpler expression that's equal to $\log(n+1)$, though. However, since you're only interested in proving that $\log(n+1)$ is “not too large”, it can be a good strategy to find an intermediate step that's larger than $\log(n+1)$ but still not too large. That is, try to find a function $f$ such that $\log(n+1) \le f(n)$ (for sufficiently large $n$), and $f(n) \in O(\log n)$.

(Easy exercise: prove that this is true — if you've found a such a function $f$ then $\log(n+1) \in O(\log n)$.)

So you can try to fill in the statement $\log(n+1) \le \ldots$ with something simpler on the right-hand side. “Simpler” meaning that in the end it'll be simpler to prove that this is in $O(\log n)$. So keep the definition of $O$ in mind: you'll need to prove that $f(n) \le C \log n$ for some $C \gt 0$.

This suggests trying to find $f$ of the form $C \log(n)$.

Hint:

$x + 1 \le x + x$

Hint #2:

You can say that again.

Of course this approach works for other functions and other bounds.

Exercise (open-ended): can you generalize this to $\Omega$? To $\Theta$? To $o$?

Simplify is only necessary if you can show the same with less steps. Here simplifying will not spare you something.

You can either find a $$c$$ and $$n$$ or you could use limit value.

$$v = \lim_{n\to\infty}{\frac{\log(n+1)}{\log(n)}}$$

and if the limits exist ($$v < \infty$$) then $$\log(n+1)\in O(\log(n))$$.

• That formula does not make any sense; you can not divide infinity by infinity. I guess you want to propose what's explained here?
– Raphael
Mar 8, 2016 at 19:57
• Also, what do you mean by "$\lim(n)$"? Do you mean something like $\lim_{n\to\infty}f(n)$, where $f$ is some function such as $\log$? Mar 8, 2016 at 20:27
• @Raphael Yes, I'm sorry I meant $\log$ of course! Mar 8, 2016 at 23:29

You can simplify the expression as following:

$$\log(n+1)=\log(n)+\log \left(\frac{n+1}{n}\right)$$

It shouldn't be to hard to show that $\log \left(\frac{n+1}{n}\right)<\log(n)$ for $n\geq 2$.

But it doesn't necessarily help to make the process shorter.

However, to solve the problem, you need to rewrite something. This can be done with inequalities or with equalities. In this case, I'd personally prefer to start out with inequalities.

• and $\log(1 + 1/n) < 2 < \log n$ if $n$ is large enough, done. Mar 9, 2016 at 16:33
• @vonbrand Exactly, but I usually leave those details out so that the OP can figure them out. Otherwise they won't think about the answer. Mar 9, 2016 at 17:08

$$n+1 ≤ n^2$$ for $$n ≥ 2$$, therefore $$\log(n+1) ≤ \log (n^2) = 2 \log n$$ for $$n ≥ 2$$, which by definition means $$\log(n+1) = O(\log n)$$.

“Simplifying” is difficult. Let $$f(n) = 2^{2^n}$$, then $$f(n+1) ≠ O(f(n))$$. Same for $$f(n) = n!$$ Or more difficult to prove when $$f(n) = \left|\sin(n)\right|$$.