0

This seems a bit weird. I thought that $\frac{n^3}{\log(n)}$ is tight bounded by $n^3$ since its upper bound should also be $n^3$ and it's lower bound can be for example $\frac{1}{2}$

However, I realized that as $n$ grows larger, $\frac{n^3}{2}$ would actually surpass $\frac{n^3}{\log(n)}$. So what I want to know is if there exists a tight-bound for $\frac{n^3}{\log(n)}$, or for that case for any rational expression and the behaviours for bounds on rational expressions. (since it seems like any constant will eventually be so little compared to a moving variable).

Furthermore, does this mean that the lower bound for $\frac{n^3}{\log(n)}$ is $n^2$?

Gary
  • 31,845
q.Then
  • 3,080
  • 1
    $\frac{n^3}{\log n}$ is already a nice expression. The function $n^2$ is after a while (the while depends on the base of the log) a lower bound, but a fairly poor one. After a while, $n^{2.9}$ is a lower bound. – André Nicolas Oct 29 '15 at 21:38

1 Answers1

1

$\log{n}$ grows more slowly than any positive power of $n$ (you can check this by differentiating, for example). Therefore for every $\epsilon > 0$, then for sufficiently large $n$,

$$ \frac{n^3}{\log{n}} > n^{3 - \epsilon}$$

This is why when people look at computational complexity, logarithmic terms are sometimes not considered bad.

Christopher A. Wong
  • 22,445
  • 3
  • 51
  • 82