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

1. Jul 10, 2012

### 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!

2. Jul 11, 2012

### chiro

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.

3. Jul 11, 2012

### scorpion4377

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.

4. Jul 11, 2012

### mathman

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.

5. Jul 11, 2012

### scorpion4377

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.

6. Jul 12, 2012

### mathman

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+ε

7. Jul 13, 2012

### haruspex

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

8. Jul 13, 2012

### scorpion4377

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.

$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!

Last edited: Jul 13, 2012
9. Jul 13, 2012

### scorpion4377

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.

10. Jul 13, 2012

### mathman

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
11. Jul 13, 2012

### scorpion4377

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

I see now. Sorry for the misunderstanding!