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 , 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.
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 . However, holds only for . In fact, is not a proposition; it is neither true nor false and turns into one or the other only after fixing . So, strictly speaking, one needs to specify such that the inequality holds for all or at least say that such 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 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 .
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 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 .