2
$\begingroup$

I'm not very certain about how to deal with asymptotics when they are in the denominator. For $$O\left(\frac{n^2}{\log{\frac{n(n+1)}{2}}}\right)$$, my intuition tells me that it should be treated in a similar way as little o. Would that be correct?

Also, is this in any way comparable with $O(n)$ or $O(n^2)$?

$\endgroup$
5
$\begingroup$

Your expression is

$$ E = \frac{cn^2}{\log \frac{n(n+1)}{2}}$$

where $c$ is some constant. The simple upper bound for $E$ is

$$ E\le c n^2$$

which implies that $\mathcal{O}(n^2)$. For a better bound

$$E = \frac{cn^2}{\log \frac{n(n+1)}{2}} = \frac{cn^2}{ 2 \log n + \log n - \log 2 } $$

Now it is an easy verification that $E$ is $\mathcal{O}(\frac{n^2}{\log n})$. In other words $E$ is $o(n^2)$(weaker statement as compare to the previous one).

$\endgroup$
  • $\begingroup$ You can't express $\log(n^2 + n)$ as $\log n^2 + \log n$ that would be equal to $3\log n = \log n^3$. But surely you can ignore the smaller summand. That is, the final result is correct. $\endgroup$ – Albjenow Jan 9 at 13:09

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.