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

a n^2 + b n + c \in \Omega(n^2)

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

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

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

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

I understand that they picked c_1 and c_2 (almost) arbitrarily. However, I just can't see how they picked their lower limit on n 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 n_0^*. 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
a n^2 + b n + c \in \Omega(n^2)
Of course, this is equivalent to saying that there exists c_1, c_2 \in ℝ^+ such that

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

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

First, need to specify that a > 0.

This would imply that
0 \leq a n^2/4 \leq a n^2 + b n + c \leq 7a n^2/4 for all n \geq n_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 a n^2/4 \leq a n^2 + b n + c. It would follow from 0 \leq 3a n^2 + 4b n + 4c. 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:
3a n^2 + 4b n + 4c = (2a n^2 + 4b n) + (a n^2 + 4c)
2a n^2 + 4b n \geq 4|b|n + 4bn \geq 0
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.

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

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

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 n. 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!