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
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
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.
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.
Yes.so n^3 is the right bound?
Yes, with two caveats. These particular inequalities are true for all $\displaystyle n\in\mathbb{N}$. However, $\displaystyle n^3 > 7n^2$ holds only for $\displaystyle n > 7$. In fact, $\displaystyle n^3 > 7n^2$ is not a proposition; it is neither true nor false and turns into one or the other only after fixing $\displaystyle n$. So, strictly speaking, one needs to specify $\displaystyle n_0$ such that the inequality holds for all $\displaystyle n>n_0$ or at least say that such $\displaystyle n_0$ exists.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$.
I just dropped it to give a rough illustration. Of course, these terms have to be accounted for.Where did the nlgn + 10 go?
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.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$.