Analysis · O, Θ & Ω

Asymptotic Bounds Lab

Choose a running-time function f(n) and a reference growth function g(n). Explore constant multiples and the threshold n₀. Separate the mathematical asymptotic relationship from what a finite plot can demonstrate.

Function f(n)

Reference g(n)

Bound to display

Lower constant c₁ > 0

Upper constant c₂ > 0

Threshold n₀

Plot through n =

Logarithmic y-axis

Definition and asymptotic relationship

Functions and chosen bounds

f(n) · solid bluec₁g(n) · dashed greenc₂g(n) · dashed red

The shaded region is n ≥ n₀. Curves connect integer samples. A finite sample can disprove these chosen constants with a counterexample; passing all displayed points does not prove a bound for every n ≥ n₀.

Beyond the graph

These classifications come from the known formulas and eventual growth of f(n)/g(n), not from fitting the plot. A wrong choice of constants does not make a true asymptotic relationship false: the definitions require that suitable constants exist.

Common distinctions

O is an asymptotic upper bound; it need not be tight.
Ω is an asymptotic lower bound.
Θ gives matching upper and lower growth bounds.
O does not mean “worst case,” and Ω does not mean “best case.” First choose the running-time function being bounded.