1
$\begingroup$

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.

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

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

$\endgroup$
-1
$\begingroup$

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.