1
$\begingroup$

Would $\log_2 (n+1)$ simplify to $\mathcal{O}(\log_2 n)$? I wasn't sure if this was valid since logs aren't distributive and I couldn't find a constant $c$ relating the expressions.

If this turns out to be valid, could you include the constant that relates the expressions?

3 Answers 3

4

For positive integers $n$ you have $\log_2(n+1)\le\log_2(2n)=1+\log_2n$, and $1+\log_2n\le2\log_2n$ for $n\ge 2$. Thus, $\log_2(n+1)$ is indeed $O(\log_2n)$.

2

You in fact have $\log_2(n+1) = \log_2(n) + \mathcal{O}\left(\dfrac1n \right)$ and hence $\log_2(n+1) \sim \log_2(n)$. This is so since $\log_2(n+1) = \log_2 \left(n (1+1/n) \right) = \log_2(n) + \log_2 \left(1 + \dfrac1n \right) = \log_2(n) + \mathcal{O} \left(\dfrac1n \right)$

1

Well for $n\geq 2$ we have that log$_2(n+1) \leq \text{log}_2(n^2) = 2\text{log}_2(n)$.

So yes you are right.