2
$\begingroup$

Consider the following functions:

$f(n) = \frac{n^2}{\log n}$

$g(n) = n(\log n)^2$

Indicate the relation between the two (e.g. $f(n)= O(g)$, $f = Ω(g)$ or $f = Θ(g)$)

The above functions are relatively complicated to visualize. In such cases, how would one go about identifying the relation between the functions? (Its hard to predict the behaviour of these functions without a graphing calculator, at least for someone with my mathematical knowledge).

  • 0
    I have written out a more formal answer. But finding out what's really happening was done informally. That led to the more formal writeup. Finding out how the *ratio* behaves is generally a good idea, since that is how the various relatives of "big O" are defined.2012-10-08

1 Answers 1

1

Let $H(n)=\frac{g(n)}{f(n)}$. Then $H(n)=\frac{(\log n)^3}{n}.$ As $n\to\infty$, $H(n)\to 0$. This can be shown in various ways. One of the simpler ones is to let $x=\log n$. Then $n=e^x$, and we are interested in $\lim_{x\to\infty}\frac{x^3}{e^x}.$ Now we can use L'Hospital's Rule $3$ times. Or else note that by the Taylor expansion of $e^x$, for $x$ positive we have $e^x\gt 1+x+\frac{x^2}{2}+\frac{x^3}{6}+\frac{x^4}{24}\gt \frac{x^4}{24}$, and therefore $\frac{x^3}{e^x}\lt \frac{24}{x}.$ It is clear that $\frac{24}{x}\to 0$ as $x\to\infty$.

Remark: Here is a general heuristic. Informally, for large enough $n$ the number $\log n$ is negligible compared to any positive power of $n$, like $n^{0.01}$. So $n^2/(\log n)$ is much larger than $n(\log n)^2$.

Since "big O" and all its relatives are defined in terms of ratios, looking at $g(n)/f(n)$, or $f(n)/g(n)$, is a natural first step.