Questions about Big Oh notation

  • Context: Undergrad 
  • Thread starter Thread starter AxiomOfChoice
  • Start date Start date
  • Tags Tags
    Notation
Click For Summary
SUMMARY

The discussion focuses on verifying two assertions related to Big Oh notation: (\mathcal O(\epsilon))^2 = \mathcal O(\epsilon^2) and \sqrt{1 + \mathcal O(\epsilon^2)} = 1 + \mathcal O(\epsilon^2). The first assertion is proven by demonstrating that if f(\epsilon) = \mathcal O(\epsilon), then f^2(\epsilon) = \mathcal O(\epsilon^2) holds true. The second assertion is validated using the binomial expansion, confirming that the approximation is accurate as \epsilon approaches zero.

PREREQUISITES
  • Understanding of Big Oh notation
  • Familiarity with limits and asymptotic analysis
  • Knowledge of binomial expansion
  • Basic calculus concepts
NEXT STEPS
  • Study the properties of Big Oh notation in algorithm analysis
  • Learn about asymptotic notations: Big Theta and Big Omega
  • Explore the application of binomial expansion in mathematical proofs
  • Investigate advanced topics in limits and continuity
USEFUL FOR

Students, mathematicians, and computer scientists interested in algorithm analysis, particularly those looking to deepen their understanding of asymptotic notation and its applications in performance evaluation.

AxiomOfChoice
Messages
531
Reaction score
1
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:

[tex] (\mathcal O(\epsilon))^2 = \mathcal O(\epsilon^2)[/tex]

and

[tex] \sqrt{1 + \mathcal O(\epsilon^2)} = 1 + \mathcal O(\epsilon^2)[/tex]

Thanks so much.
 
Physics news on Phys.org
I think I've managed to show the first one. Suppose [itex]f(\epsilon) = \mathcal O(\epsilon)[/itex] (as [itex]\epsilon \searrow 0[/itex]). Then there exists [itex]C >0, \delta > 0[/itex] such that [itex]0 < \epsilon < \delta[/itex] implies

[tex] \left| \frac{f(\epsilon)}{\epsilon} \right| \leq C.[/tex]

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

[tex] \left| \frac{f^2(\epsilon)}{\epsilon^2} \right| \leq C^2.[/tex]
 
The second approximation can be gotten by using the binomial expansion of the left side.
 

Similar threads

  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 0 ·
Replies
0
Views
2K
  • · Replies 3 ·
Replies
3
Views
1K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 6 ·
Replies
6
Views
3K
  • · Replies 2 ·
Replies
2
Views
1K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K