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

[S.N.]

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.

 

[mighty2000]

Thank you for your question regarding the comparison of a polynomial function and a logarithmic function in terms of growth rate. I can assure you that this is a very important concept in mathematics and is often used in analyzing algorithms and their efficiency.

Firstly, I would like to clarify that the term "big oh" (O) is used to describe the upper bound of the growth rate of a function. In other words, it is a measure of the worst-case scenario for the growth of a function. Therefore, when we say that a polynomial "grows faster" than a logarithmic function, we mean that the polynomial has a higher growth rate compared to the logarithmic function.

To formally prove that a polynomial function grows faster than a logarithmic function, we can use the limit definition of big oh. This states that a function f(x) is in the set O(g(x)) if and only if there exists a constant c and a natural number m such that for all x greater than m, f(x) is less than or equal to c*g(x).

In your case, we are comparing the functions n^0.01 and (log(n))^10. To prove that n^0.01 is in the set O((log(n))^10), we need to find a suitable constant c and natural number m that satisfies the above definition.

Let us start by considering the limit of the ratio of these two functions as x approaches infinity:

lim (n^0.01)/(log(n))^10 as n->infinity

Using L'Hopital's rule, we can evaluate this limit as:

lim (0.01*n^(-0.99))/(10*(log(n))^9/(n))

= lim (0.01*n^(-0.99))/(10*(log(n))^9/(n))

= lim (0.01*(-0.99)*n^(-1.99))/(10*9*(log(n))^8/(n^2))

= lim (-0.0099*n^(-2.99))/(90*(log(n))^8)

= lim (-0.00011*n^(-3.99))/(720*(log(n))^7)

This process can be repeated until we get a limit of 0, which means that n^0.01 grows at a much faster rate compared to (log(n))^10. Therefore, we can choose any value of c (e.g. 1) and