1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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...