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 $\displaystyle n^3$, $\displaystyle n^2$ and $\displaystyle n\lg n$ 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) $\displaystyle x^n$ will beat $\displaystyle x^k$ for any $\displaystyle k<n$. In turn $\displaystyle x^k$ will beat $\displaystyle \log x^m$ for all $\displaystyle k$ and $\displaystyle m$. 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 $\displaystyle n$ that counts, people use big-O, small-O and similar concepts instead of pointwise inequalities (i.e., inequalities for each particular $\displaystyle n$). By definition, these concepts allow the required inequality to fail on a finite initial interval.

Second, saying that $\displaystyle n^3 > 7n^2$ does not guarantee that $\displaystyle n^3$ is a tight bound. You need to say something about the other inequality, i.e., why $\displaystyle Cn^3 < n^3 - 7n^2$ for large $\displaystyle n$ and some $\displaystyle C$. - 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 $\displaystyle n^3$ from the start. We need to compare $\displaystyle n^3$ and $\displaystyle n^3 - 7n^2 + n\lg n + 10$. The intuitive idea is that $\displaystyle 7n^2$, which is subtracted, will eventually dominate $\displaystyle n\lg n +10$, so we should eventually have

(1) $\displaystyle n^3>n^3 - 7n^2 + n\lg n + 10$

On the other hand, $\displaystyle n^3=1/2n^3+1/2n^3$, and one of those $\displaystyle 1/2n^3$ eventually dominates $\displaystyle -7n^2+n\lg n+10$; therefore, we should have

(2) $\displaystyle 1/2n^3<1/2n^3+1/2n^3 - 7n^2 + n\lg n + 10$

To prove (1), one must show that eventually $\displaystyle 7n^2>n\lg n+10$. A typical method is to use more significant terms as bounds for less significant ones. So, find $\displaystyle n_0$ such that $\displaystyle n\lg n > 10$ for $\displaystyle n > n_0$. Then $\displaystyle n\lg n + 10 < 2n\lg n$ for $\displaystyle n>n_0$. Next, find $\displaystyle n_1>n_0$ such that $\displaystyle 7n^2>2n\lg n$, i.e., $\displaystyle n>3/2\lg n$ for $\displaystyle n>n_1$. Thus, for $\displaystyle n>n_1$ we have $\displaystyle 7n^2>n\lg n+10$.

The statement (2) is equivalent to $\displaystyle 1/2n^3>7n^2-n\lg n-10$. This is, of course, implied by $\displaystyle 1/2n^3>7n^2$, i.e., $\displaystyle n>14$.

So, for $\displaystyle n>\max(n_1,14)$ both (1) and (2) are true, which means that $\displaystyle n^3$ is an asymptotic tight bound for $\displaystyle n^3 - 7n^2 + nlgn + 10$.