Log n < O(n^ε) for Large n - Simple Function Growth

[ti89fr33k]

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

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

Thanks,

Mary

 

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

 

[ti89fr33k]

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

 

[ti89fr33k]

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

 

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

 

[ti89fr33k]

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

 

[ti89fr33k]

there is a pure algebra method

 

[shmoe]

If I write

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

does that help you evaluate the limit?

 

[ti89fr33k]

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

 

[ti89fr33k]

oh...i see...