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

• S.N.
In summary: O((log(n))^10).In summary, using the limit definition of big oh, we can formally prove that a polynomial function (n^0.01) grows faster than a logarithmic function ((log(n))^10). I hope this explanation has been helpful to you. Let me know if you have any further questions.Best regards,[Your Name]
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.

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

## 1. What is "Big Oh" notation?

"Big Oh" notation is a mathematical notation used to describe the limiting behavior of a function when the input approaches a certain value. It is commonly used in computer science to analyze the efficiency of algorithms and to compare the growth rates of functions.

## 2. How is "Big Oh" used to show that a polynomial grows faster than a logarithmic function?

To show that a polynomial grows faster than a logarithmic function using "Big Oh" notation, we compare the growth rates of the two functions as the input size increases. A polynomial function with a higher degree will have a higher growth rate than a logarithmic function, making it "bigger" in terms of "Big Oh". This means that the polynomial function will eventually surpass the logarithmic function in terms of growth rate.

## 3. Why is it important to understand the growth rates of functions?

Understanding the growth rates of functions is important in computer science because it allows us to analyze the efficiency of algorithms and choose the most efficient one for a given task. It also helps us understand the performance of different data structures and make informed decisions when designing and optimizing software.

## 4. What is the difference between "Big Oh" and "Big Omega" notation?

"Big Oh" and "Big Omega" are both used to describe the limiting behavior of a function, but they represent different things. "Big Oh" represents the upper bound of a function's growth rate, while "Big Omega" represents the lower bound. In other words, "Big Oh" describes the maximum growth rate of a function, while "Big Omega" describes the minimum growth rate.

## 5. Can "Big Oh" notation be used for functions other than polynomials and logarithms?

Yes, "Big Oh" notation can be used for any type of function. It is commonly used for polynomials and logarithms because these functions are commonly encountered in computer science and have well-defined growth rates. However, "Big Oh" notation can also be used for exponential, factorial, and many other types of functions to describe their growth rates.

Replies
1
Views
2K
Replies
2
Views
679
Replies
7
Views
841
Replies
1
Views
808
Replies
2
Views
235
Replies
13
Views
2K
Replies
2
Views
1K
Replies
1
Views
1K
Replies
4
Views
1K
Replies
6
Views
859