Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
Thank You for the help. –  user26649 Oct 8 '12 at 4:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.