1. ## Asymptotic 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

2. I recommend getting a little intuition about the behavior of the functions $n^3$, $n^2$ and $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) $x^n$ will beat $x^k$ for any $k. In turn $x^k$ will beat $\log x^m$ for all $k$ and $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.

3. Actually, the famous physicist Richard Feynman suggested that big numbers should be called economical instead of astronomical . So you may visualize the difference in function growth as the difference between the amount of the recent US bailout and a median salary.

4. am I safe to say:
n^3 > n^2 > nlgn?

so n^3 is the right bound?

5. so n^3 is the right bound?
Yes.

am I safe to say:
n^3 > n^2 > nlgn?
Yes, with two caveats. These particular inequalities are true for all $n\in\mathbb{N}$. However, $n^3 > 7n^2$ holds only for $n > 7$. In fact, $n^3 > 7n^2$ is not a proposition; it is neither true nor false and turns into one or the other only after fixing $n$. So, strictly speaking, one needs to specify $n_0$ such that the inequality holds for all $n>n_0$ or at least say that such $n_0$ exists.

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

Second, saying that $n^3 > 7n^2$ does not guarantee that $n^3$ is a tight bound. You need to say something about the other inequality, i.e., why $Cn^3 < n^3 - 7n^2$ for large $n$ and some $C$.

6. 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?

7. Where did the nlgn + 10 go?
I just dropped it to give a rough illustration. Of course, these terms have to be accounted for.

C1n^3 <= n^3 - 7n^2 <= C2n^3
C1 <= -7/n <= C2 [dividing all n^3 throughout]
This should be C1 <= 1 - 7/n <= C2. If you have this (again, this is only an illustration because nlgn + 10 should be there), then you can take C2 = 1. The right inequality would be true for all n. Also, you can set C1 = 1/2. For large n, 7/n is small and so 1/2 < 1 - 7/n.

However, I would not divide by $n^3$ from the start. We need to compare $n^3$ and $n^3 - 7n^2 + n\lg n + 10$. The intuitive idea is that $7n^2$, which is subtracted, will eventually dominate $n\lg n +10$, so we should eventually have

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

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

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

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

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

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