- #1

S.N.

- 22

- 0

**Big Oh: showing that a polynomial "grows faster" than any log function.**

## Homework Statement

is n^0.01 big oh of (log(n))^10 ?

***Bear in mind, the log is a binary log.

## Homework Equations

the formal statement would be...

does

n^0.01 < c(log(n))^10

hold for all n greater than a natural number m and c being a constant?

## The Attempt at a Solution

I'm sure it isn't big oh. What I'm confused about is showing this in a nice, formal manner. I know that a polynomial function won't be bounded by a log function, but I'm trying to think of a satisfying proof for it. here's my approach thus far:

let t=log(x), so 2^t = x

then we look at

2^0.01t < ct^10

which is equivalent to looking at

(2^0.01t)/(t^10) < c

which just isn't true for big enough t. But I don't think that's a very formal approach. I know that 2^(t*k) where k is a constant will "grow faster" than any t^g where g is another constant, but how can I prove this for sure? Do I have to bust out the real analysis toolkit or something (shouldn't have to, this is for a discrete course)?

Any insight (or better approach) is much appreciated.