# 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
And not all MSErs are guys. –  Did Feb 20 '13 at 12:44
Since you are new to this site, please consider reading this: How to ask a homework question?. In particular, you should use homework tag if your question comes from a homework. –  Martin Sleziak Feb 20 '13 at 13:18
Jenna, you shouldn't edit your question to be so different from the one that was answered. If you want to ask a new, related question, then post a new question using the ASK QUESTION link under the MATHEMATICS banner. I'm going to revert the edit you've made. –  Antonio Vargas May 6 '13 at 19:40
@Did: Many native speakers do use guys for both sexes. –  Brian M. Scott May 6 '13 at 19:57

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))$.

-