Results 1 to 7 of 7

Math Help - Asymptotic Bound

  1. #1
    Member
    Joined
    Sep 2007
    Posts
    222

    Question 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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    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<n. 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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2007
    Posts
    222

    Question

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

    so n^3 is the right bound?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Sep 2007
    Posts
    222

    Question

    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Asymptotic
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: March 30th 2011, 12:02 AM
  2. Replies: 0
    Last Post: February 19th 2010, 01:06 AM
  3. greatest least bound and least upper bound proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 4th 2009, 04:44 PM
  4. Upper bound/Lower bound?
    Posted in the Pre-Calculus Forum
    Replies: 7
    Last Post: September 13th 2009, 10:48 AM
  5. least upper bound and greatest lower bound
    Posted in the Calculus Forum
    Replies: 2
    Last Post: September 22nd 2007, 09:59 AM

Search Tags


/mathhelpforum @mathhelpforum