Proving that $h=O(\log_2 n)$ if $h=\log_2 (n+1)$

Question

Suppose that $h=\log_2 (n+1)$. Why is $h$ also $O(\log_2 n)$?

I know the definition of big $O$ notation, and properties or logarithms, but I can't figure it out - that $+1$ is causing troubles.

score 3 · Answer 1 · answered Jun 17 '16 at 17:04

3

$\log_2(n+1) < \log_2(n^2) = 2\log_2(n)$ for sufficiently large $n$.

answered Jun 17 '16 at 17:04

Robert Israel

1

Sufficiently larger than $2$, even. :) For $n\geq 2$, $$n^2 \geq 2n \geq n+n \geq n+1.$$ – Clement C. Jun 17 '16 at 17:33

score 1 · Answer 2 · answered Jun 17 '16 at 17:04

1

That's because $\log_2(n+1)\sim_\infty\log_2n$.

answered Jun 17 '16 at 17:04

Bernard

While it's completely correct, the question has a flavor indicating that equivalents are outside the scope (the statement to prove is strictly weaker than the one above). – Clement C. Jun 17 '16 at 17:34
Yes, but one can mimic equivalent, thereby proving the existence of a constant $C$. – Bernard Jun 17 '16 at 18:11

score 1 · Answer 3 · answered Jun 17 '16 at 17:09

1

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

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

answered Jun 17 '16 at 17:09

YoTengoUnLCD

3 Answers3