# How does one approach asymptotic relation problems?

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

-
Informally, for large enough $n$ the number $\log n$ is negligible compared to any positive power of $n$. So $n^2/(\log n)$ is much larger than $n(\log n)^2$. – André Nicolas Oct 8 '12 at 3:55
@AndréNicolas Thank You. Using reasoning, especially for extremely complicated problems however becomes hard. Is there another approach that is easier, or is reasoning it out like you did the only way? – user26649 Oct 8 '12 at 3:57
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. – André Nicolas Oct 8 '12 at 4:09

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.