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

  • $\begingroup$ Our reference question has some tools for comparing terms asymptotically. $\endgroup$
    – Raphael
    Jan 8, 2020 at 20:21

1 Answer 1


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

  • $\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, 2020 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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