# Discrete math: Big O notation proof with logarithms

Determine whether or not the following is true: $$\log((1/n) + n^2 )$$ is $$O(\log n)$$.

I'm struggling to solve this. I'm especially confused because of the $$O(\log n)$$ and would appreciate some help or even a push in the right direction. I'm unconfident with logarithms in general which is why I'm struggling with this question in particular.

• Hint: $\dfrac1n\ll n^2$. – Yves Daoust Jun 10 '19 at 18:05
• $\log(\frac{1}{n}+n^2) < \log(n^2+n^2) = 2 \log(2) \log(n) = O( \log n)$ – katana_0 Jun 10 '19 at 18:29

$$\log((1/n) + n^2 )$$

If we just focus on the term inside of the logarithm.

$$let x = 1/n + n^2$$

As n grows, we notice that the 1/n term effectively becomes zero and the overpowering term is $$n^2$$

We can now state that $$\log((1/n) + n^2 )$$ has growth $$log(n^2)$$ when n gets large.

We know from logarithms that $$log(a^b) = b* log(a)$$

So $$log(n^2)$$ can be rewritten as $$2*log(n)$$ for large n we notice that the constant value of 2 is insignificant and can conclude that our original expression has growth $$O(log(n))$$

$$n^2+\frac{1}{n}$$ is $$O(n^2)$$.

$$\log(n^2)=2\log n$$ is $$O(\log n)$$

• The OP is clearly strugling with $O$ notations and logarithm... an explanation would be much more useful than these math lines – Thomas Lesgourgues Jun 10 '19 at 18:28