Discrete math: Big O notation proof with logarithms

216 Views Asked by At

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.

2

There are 2 best solutions below

0
On BEST ANSWER

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

1
On

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

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