Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Solving a simple inequality arising from the study of algorithms -asymptotic notation

  1. Jul 10, 2012 #1
    Hey everybody,

    I'm a little embarrassed to be asking this question as I feel it is extremely easy, but I will do so anyway. I'm self studying some algorithms, and the book that I'm using claims that

    [itex]a n^2 + b n + c \in \Omega(n^2)[/itex]

    Of course, this is equivalent to saying that there exists [itex] c_1, c_2 \in ℝ^+[/itex] such that

    [itex] 0 \leq c_1 n^2 \leq a n^2 + b n + c \leq c_2 n^2 [/itex] for all [itex] n \geq n_0^* [/itex]

    In order to verify this, the book says that I should let [itex] c_1 = a/4 [/itex], [itex] c_2 = 7a/4[/itex] and [itex] n \geq 2 \cdot max(|b|/a, \sqrt{|c|/a})[/itex]. This would imply that

    [itex] 0 \leq a n^2/4 \leq a n^2 + b n + c \leq 7a n^2/4 [/itex] for all [itex] n \geq n_0^* [/itex]

    I understand that they picked [itex] c_1 [/itex] and [itex] c_2 [/itex] (almost) arbitrarily. However, I just can't see how they picked their lower limit on [itex] n[/itex] given these two constants. I've been messing around with the quadratic equation for a little while now and I just fail to see it.

    Any help would be appreciated! I just want to understand the logic of their selection of [itex] n_0^*[/itex]. THanks!
     
  2. jcsd
  3. Jul 11, 2012 #2

    chiro

    User Avatar
    Science Advisor

    Re: Solving a simple inequality arising from the study of algorithms -asymptotic nota

    Hey scorpion4377 and welcome to the forums.

    I'm thinking that it has to do with the quadratic term of taking an^2 + bn + c into (SQRT(a)n + d)^2 + e for some d and e. You can then show that that this term is greater than or equal to an^2 but less than or equal to some other multiple of n^2.

    Do you have any extra information for the coeffecients? I'm assuming (but this may be wrong) that a,b,c are all >= 0 and if this is the case you can get an upper bound for a constant that bounds the expression.

    One example to bound the upper limit is to take say (xn + y)^2 and choose a value of (zn)^2 where zn > xn + y which implies z > (xn + y)/n = (xn/n) + (y/n) = x + y/n.
     
  4. Jul 11, 2012 #3
    Re: Solving a simple inequality arising from the study of algorithms -asymptotic nota

    Thanks for your response! I'll take a closer look at it when I get out of work =P

    The problem states that a > 0, but there are no restrictions on the other two coefficients.
     
  5. Jul 11, 2012 #4

    mathman

    User Avatar
    Science Advisor
    Gold Member

    Re: Solving a simple inequality arising from the study of algorithms -asymptotic nota

    For large enough n, an2 completely dominates the quadratic, so c1<a<c2. will always work.
     
  6. Jul 11, 2012 #5
    Re: Solving a simple inequality arising from the study of algorithms -asymptotic nota

    That's exactly what the "informal" use of theta notation shows. I totally understand (and believe) the informal justification, but I'm having trouble with showing it formally.
     
  7. Jul 12, 2012 #6

    mathman

    User Avatar
    Science Advisor
    Gold Member

    Re: Solving a simple inequality arising from the study of algorithms -asymptotic nota

    For any ε > 0 and n > N(ε), |bn + c| < εn2, so c1 = a-ε and c2 = a+ε
     
  8. Jul 13, 2012 #7

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Re: Solving a simple inequality arising from the study of algorithms -asymptotic nota

    First, need to specify that a > 0.
    No, it doesn't imply that exactly. I does suggest that this is what you need to show.
    Let's work that backwards a bit for [itex] a n^2/4 \leq a n^2 + b n + c [/itex]. It would follow from [itex] 0 \leq 3a n^2 + 4b n + 4c [/itex]. The form of the lower bound for n suggests we need to break the b and c terms apart so that we have two expressions each ≥ 0, one involving a and b, the other involving a and c:
    [itex] 3a n^2 + 4b n + 4c = (2a n^2 + 4b n) + (a n^2 + 4c)[/itex]
    [itex] 2a n^2 + 4b n \geq 4|b|n + 4bn \geq 0[/itex]
    See if you can apply this approach to get the rest.
     
  9. Jul 13, 2012 #8
    Re: Solving a simple inequality arising from the study of algorithms -asymptotic nota

    Oops. I didn't mean to imply that it's already true, but instead that it is what I still have to show. I see where you are coming from now.

    [itex] 2a n^2 + 4b n \geq 4|b|n + 4bn \geq 0[/itex] is true if [itex]2a n^2 \geq 4|b|n[/itex]. This would be true assuming that [itex] n \geq 2|b| / a [/itex]. On the other hand:
    [itex]an^2 + 4c \geq 4|c|+ 4c \geq 4 ( |c| + c ) \geq 0[/itex] if [itex] an^2 \geq 4|c| [/itex] This would imply that [itex] n \geq 2\sqrt{|c|/a}[/itex].

    And now, I see that both inequalities are true if [itex] n \geq 2 max( |b|/a, \sqrt{|c|/a}) [/itex].

    Working backwards, I could now show that the first inequality is true. I guess I would have to apply the same techniques to the other side, and I'm sure that I'd get the same bounds on [itex]n[/itex]. I will work this out on a piece of paper on my own in a bit.

    Thank you so much for your help! I really appreciate everybody's advice!
     
    Last edited: Jul 13, 2012
  10. Jul 13, 2012 #9
    Re: Solving a simple inequality arising from the study of algorithms -asymptotic nota

    Again, that's what I'm trying to prove. If I could prove this, the original theorem would be trivial for me.

    I really do appreciate the help, of course! Thanks for pointing me in the right direction.
     
  11. Jul 13, 2012 #10

    mathman

    User Avatar
    Science Advisor
    Gold Member

    Re: Solving a simple inequality arising from the study of algorithms -asymptotic nota

    |bn + c|/n2 ≤ |b|/n +|c|/n2 -> 0 monotonically.
    Fix ε, find N satisfying |b|/N +|c|/N2 < ε.

    I don't know how to formalize any further.
     
    Last edited: Jul 13, 2012
  12. Jul 13, 2012 #11
    Re: Solving a simple inequality arising from the study of algorithms -asymptotic nota

    I see now. Sorry for the misunderstanding!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Solving a simple inequality arising from the study of algorithms -asymptotic notation
  1. Solving an inequality (Replies: 5)

  2. Solving an Inequality (Replies: 8)

  3. Simple Inequality (Replies: 4)

Loading...