PDA

View Full Version : Questions about Big Oh notation


AxiomOfChoice
Nov23-10, 10:07 PM
I'm sure I could think my way through these, but I'm sick and on a tight schedule, so I was hoping someone here could help me out. I would appreciate a verification, with or without proof, of the following assertions:


(\mathcal O(\epsilon))^2 = \mathcal O(\epsilon^2)


and


\sqrt{1 + \mathcal O(\epsilon^2)} = 1 + \mathcal O(\epsilon^2)


Thanks so much.

AxiomOfChoice
Nov23-10, 10:16 PM
I think I've managed to show the first one. Suppose f(\epsilon) = \mathcal O(\epsilon) (as \epsilon \searrow 0). Then there exists C >0, \delta > 0 such that 0 < \epsilon < \delta implies


\left| \frac{f(\epsilon)}{\epsilon} \right| \leq C.


To show that (\mathcal O(\epsilon))^2 = \mathcal O(\epsilon^2), one simply observes that


\left| \frac{f^2(\epsilon)}{\epsilon^2} \right| \leq C^2.

mathman
Nov24-10, 03:50 PM
The second approximation can be gotten by using the binomial expansion of the left side.