Are the functions $\log(n + 1)$ and $\log(n^2 + 1)$ in $\mathcal{O}(\log n)$?

How to determine if the functions $\log(n + 1)$ and $\log(n^2 + 1)$ are $\mathcal{O}(\log n)$?

Are the functions $\log(n + 1)$ and $\log(n^2 + 1)$ $\mathcal{O}(\log n)$?

-
Spitting out question from you homework assignment without showing any individual effort or even proper formatting is frowned upon on this site. – nbubis Feb 20 '13 at 12:16

3 Answers

Yes. Just take c=3 in the definition of big $\mathcal{O}$.

$\log(n^3)=3 \log(n)$ dominate both..

-

Just use the fact that if

$$\lim_{n \to \infty} \frac{f(n)}{g(n)} = c,$$ then

$$f(n)=O(g(n)).$$

For instance,

$$\lim_{n \to \infty} \frac{\ln(n^2+1)}{\ln(n)}=2 \implies \ln(n^2+1)=O(\ln(n)).$$

-

Also, for any fixed positive reals $a, b, c$, $\log(an^b+c) = O(\log(n))$

To prove this, note that, for any fixed positive reals $a, b, c$, $an^b+c = an^b(1+c/(an^b)) < 2an^b$ for $c < a n^b$ or $n > (c/a)^{1/b}$.

Thus, for such $n$, $\log(an^b+c) < \log(2a n^b) < \log(n^{b+1}) = (b+1)\log(n)$ for $n > 2a$.

So, if $n > \max(2a, (c/a)^{1/b})$, $\log(an^b+c) < (b+1)\log(n)$ so $\log(an^b+c) = O(\log(n))$.

-