DAA Module 2 05

Asymptotic Notations Visualizer — Big-O, Ω, Θ

Adjust c and n₀ and watch the bounds on a graph. This builds intuition for “upper bound”, “lower bound”, and “tight bound”.

← Index Next →

1) Choose notation

2) Choose functions

3) Adjust c and n₀

c (multiplier) c = 2
Increasing c makes the bound easier to satisfy (because c·g(n) becomes larger).
n₀ (start checking from here) n₀ = 5
Increasing n₀ ignores small-n behavior (bounds are about “eventually”).
We verify the inequality for all integers n in [n₀, nMax].

Result

Adjust c and n₀ Mode: Big-O
First failing n (if any):
—

Preset examples

Graph (offline)

Blue: f(n) • Purple: c·g(n) • Shaded region starts at n₀.
Tip: We use log-y scaling automatically to keep curves visible when values explode.

Simple theory (easy language)

Big-O (Upper Bound) means: “f(n) will not grow faster than g(n) (up to a constant) after some point.”
Formally: f(n) ≤ c·g(n) for all n ≥ n₀.
Ω (Lower Bound) means: “f(n) grows at least as fast as g(n) (up to a constant) after some point.”
Formally: f(n) ≥ c·g(n) for all n ≥ n₀.
Θ (Tight Bound) means: “f(n) and g(n) grow at the same rate (within constant factors).”
Formally: f(n) is both O(g(n)) and Ω(g(n)).

Example in words

If f(n)=3n²+5n+7 and g(n)=n², then for large n: the +5n and +7 become negligible compared to n². So f(n) is Θ(n²).