1

The overall question I'd like to ask has been answered here in the accepted answer: asymptotic tight bound for quadratic functions but I'd like to focus on a sub-part of the answer that I can't understand.

Specifically, it is this part: "So we can bound from above the inside of the sqrt(...) with 4b^2".

I can't figure out how assuming that |b|/a >= sqrt(|c|/a) helps us arrive at the 4b^2 bound for the b^2-3ac term. Here's what I get:

n >= 2*(sqrt(b^2-3ac)-b)/3a

There are two cases (as the original respondent said). I'd like to understand the first one:

  1. |b|/a >= sqrt(|c|/a)

(square both sides) b^2/a^2 >= |c|/a

(multiply across by a^2) b^2 >= a^2*|c|/a

(simplify the a^2 and a) b^2 >= a*|c|

(a is positive, so a|c| >= ac) b^2 >= ac

So if we look at the inside of the original sqrt, which was b^2-3ac, we have

b^2-3ac is >= -2ac

Not 4b^2 as indicated in the original response.

Could someone help me understand where I have gone wrong?

Thanks!

Community
  • 1
  • 1
Dan
  • 135
  • 1
  • 6
  • 1
    Now this is probably better asked on [cs.se]. That site didn't exist when the linked question was asked. –  Jul 05 '14 at 14:53
  • Oops, thanks! Should I delete this question and re-post, or is there a way to move it? – Dan Jul 05 '14 at 15:12
  • In that original post there's no indication of a > 0, which sure is essential for your deduction. – laune Jul 05 '14 at 15:12
  • You are right: I forgot to mention that. We can assume a > 0 because otherwise the function is asymptotically negative. – Dan Jul 05 '14 at 15:14
  • The original derivation seems rather cumbersome. If you determine the apex of the hyperbola and transfer it so that the apex coincides with the origin, you'll get (in the new coordinate system) y = ax^2. You can increase a by epsilon > 0 and transfer back, and that function will be an upper bound for the original ax2+bx+c. Any convenient value for epsilon will be good. Same for the lower bound. – laune Jul 05 '14 at 15:57
  • Thanks, though I'm lost here! I'll pursue this, though I feel that I'm just missing something small in the solution that I posted. I'd ideally be looking for a solution that makes mine correct (and hence makes the original poster's derivation correct). Thanks! – Dan Jul 05 '14 at 16:04

1 Answers1

2

There are two assumptions made in the answer : "we have a positive leading coefficient polynomial", i.e., a>0 and |b|/a >= sqrt(|c|/a).

Here's the derivation(each step implies the next) :

|b|/a >= sqrt(|c|/a)
b^2/a^2 >= |c|/a, (squaring both sides)
b^2 >= |c|*a, (multiplying by a^2, since a^2>=0)
3b^2 >= 3*a*|c| = |3*a*c|, since a>0
b^2 + 3b^2 >= b^2 + |3*a*c| == b^2 + |-3*a*c| >= b^2 - 3*a*c, since |x| + |y| >= |x+y|

The derivation you have shown isn't incorrect. It simply doesn't give you a bound that lets you proceed.

Pradhan
  • 16,391
  • 3
  • 44
  • 59
  • Thankyou! I'm slightly unsure of the final step, where you use |x| + |y| >= |x+y|. Wouldn't you simply use |x| >= x, and therefore |-3*a*c| >= -3ac? – Dan Jul 06 '14 at 16:27
  • You are right :) You can simply use that here since the "y" is also "|y|". – Pradhan Jul 06 '14 at 17:08