Solving Inequalities Arising from Algorithms Study

[scorpion4377]

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!

 

[chiro]

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.

 

[scorpion4377]

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.

 

[mathman]

For large enough n, an² completely dominates the quadratic, so c₁<a<c₂. will always work.

 

[scorpion4377]

For large enough n, an² completely dominates the quadratic, so c₁<a<c₂. will always work.

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.

 

[mathman]

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.

For any ε > 0 and n > N(ε), |bn + c| < εn², so c₁ = a-ε and c₂ = a+ε

 

[haruspex]

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].

First, need to specify that a > 0.

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]

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.

 

[scorpion4377]

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!

 

[scorpion4377]

For any ε > 0 and n > N(ε), |bn + c| < εn², so c₁ = a-ε and c₂ = a+ε

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.

 

[mathman]

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

I don't know how to formalize any further.

 

[scorpion4377]

I see now. Sorry for the misunderstanding!