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