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!