How do I simplify $O\left({n^2}/{\log{\frac{n(n+1)}{2}}}\right)$
-
28-09-2020 - |
Pergunta
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)$?
Solução
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).