I have f(n) = n^3 - 7n^2 + nlgn + 10

I have to state what i think the asymptotic tight bound for the above is. What would it be? My guess would be g(n) = nlgn?

Then how do i prove it like this:

C1g(n) <= n^3 - 7n^2 + nlgn + 10 <= C2g(n)

?

Thanks

Printable View

- Apr 5th 2010, 10:18 PMtaurusAsymptotic Bound
I have f(n) = n^3 - 7n^2 + nlgn + 10

I have to state what i think the asymptotic tight bound for the above is. What would it be? My guess would be g(n) = nlgn?

Then how do i prove it like this:

C1g(n) <= n^3 - 7n^2 + nlgn + 10 <= C2g(n)

?

Thanks - Apr 6th 2010, 02:13 AMemakarov
I recommend getting a little intuition about the behavior of the functions , and by plotting their graphs. You can do this, for example, in Excel or online at Function Grapher Online (just found this site). There is also a List of information graphics software in Wikipedia.

The goal of this is not to lower the standards of rigor and to give proofs in terms of one picture. Rather, it helps to appreciate to what extend some functions dwarf others when arguments become large.

A brief answer is that (I assume that all numbers are positive) will beat for any . In turn will beat for all and . When the function arguments become sufficiently large, the dominant function would tell you, for example, whether you are near Mars or near Jupiter while a lower-order function will describe the location of your friend on Earth who went to the nearest grocery to by milk. - Apr 6th 2010, 02:21 AMemakarov
Actually, the famous physicist Richard Feynman suggested that big numbers should be called economical instead of astronomical (Evilgrin). So you may visualize the difference in function growth as the difference between the amount of the recent US bailout and a median salary.

- Apr 6th 2010, 10:10 PMtaurus
am I safe to say:

n^3 > n^2 > nlgn?

so n^3 is the right bound? - Apr 7th 2010, 01:08 AMemakarovQuote:

so n^3 is the right bound?

Quote:

am I safe to say:

n^3 > n^2 > nlgn?

That is why, when comparing functions and when it is the behavior at large that counts, people use big-O, small-O and similar concepts instead of pointwise inequalities (i.e., inequalities for each particular ). By definition, these concepts allow the required inequality to fail on a finite initial interval.

Second, saying that does not guarantee that is a tight bound. You need to say something about the other inequality, i.e., why for large and some . - Apr 7th 2010, 01:18 AMtaurus
Where did the nlgn + 10 go?

so assuming i got rid of the above:

C1n^3 <= n^3 - 7n^2 <= C2n^3

C1 <= -7/n <= C2 [dividing all n^3 throughout]

How do I go on is what confuses me? - Apr 7th 2010, 02:41 AMemakarovQuote:

Where did the nlgn + 10 go?

Quote:

C1n^3 <= n^3 - 7n^2 <= C2n^3

C1 <= -7/n <= C2 [dividing all n^3 throughout]

However, I would not divide by from the start. We need to compare and . The intuitive idea is that , which is subtracted, will eventually dominate , so we should eventually have

(1)

On the other hand, , and one of those eventually dominates ; therefore, we should have

(2)

To prove (1), one must show that eventually . A typical method is to use more significant terms as bounds for less significant ones. So, find such that for . Then for . Next, find such that , i.e., for . Thus, for we have .

The statement (2) is equivalent to . This is, of course, implied by , i.e., .

So, for both (1) and (2) are true, which means that is an asymptotic tight bound for .