Simple function growth

1. Mar 28, 2005

ti89fr33k

Show log n < O(n^epsilon) for n sufficiently large.

Not actually calculus, but it has something to do with limits, so there. :rofl:

Thanks,

Mary

2. Mar 28, 2005

shmoe

Did you try looking at

$$\lim_{n\rightarrow\infty}\frac{\log n}{n^\epsilon}$$

If you can evaluate this limit, the bound you're after follows.

3. Mar 28, 2005

ti89fr33k

I know the limit is 0...but how do you evaluate it?

4. Mar 28, 2005

ti89fr33k

The answer is quite intuitive...but i want a rigorous method

5. Mar 28, 2005

shmoe

l'hopital's rule will handle the limit.

Are you able to convert from the limit to the big-O bound? This will follow from the definition of the limit.

6. Mar 28, 2005

ti89fr33k

yes, but my instructor specifically mentioned not to use l'hopitals rule

7. Mar 28, 2005

ti89fr33k

there is a pure algebra method

8. Mar 28, 2005

shmoe

If I write

$$\log n=\frac{2}{\epsilon}\log n^\frac{\epsilon}{2}$$

9. Mar 28, 2005

ti89fr33k

log n^epsilon/2 has to grow slower than n^epsilon?

10. Mar 28, 2005

ti89fr33k

oh...i see...