Design & Analysis of Algorithms

Asymptotic Order of Growth

Big oh, Omega, and Theta

What does it mean for t(n) to be in O(g(n))?

t(n) is bounded above by some constant multiple of g(n) for all sufficiently large n.

What does the set O(g(n)) actually represent?

g(n) must grow at least as fast as t(n) — g(n) is an asymptotic upper bound on t(n).

In t(n) ≤ c·g(n) for all n ≥ n0, what do c and n0 represent?

c is a positive constant multiplier; n0 is the point after which the inequality holds for all larger n

To prove 100n + 5 ∈ O(n²), what's the key inequality chain?

100n + 5 ≤ 100n + n (for n ≥ 5) = 101n ≤ 101n²

Since 101n ≤ 101n² for n ≥ 1, chaining the two inequalities proves the bound.

What values of c and n0 does that proof give for 100n + 5 ∈ O(n²)?

c = 101, n0 = 5

Are the constants c and n0 in a Big-O proof unique?

No — the definition allows freedom in choosing c and n0; multiple valid pairs can work

Different valid inequality chains can lead to different but equally correct (c, n0) pairs.

What's an alternate pair of constants proving 100n + 5 ∈ O(n²), using 100n + 5 ≤ 100n + 5n (for n ≥ 1) = 105n?

c = 105, n0 = 1

In plain terms, what must be true of g(n) relative to t(n) for t(n) ∈ O(g(n))?

g(n) must grow at least as fast as t(n) — it's an asymptotic upper bound

Big-O captures an upper bound on growth rate, not an exact match.

What does it mean for t(n) to be in Ω(g(n))?

t(n) ≥ c·g(n) for all n ≥ n0, for some positive constant c and nonnegative integer n0

This is the formal definition of Big-Omega: t(n) is bounded below by a constant multiple of g(n) for all sufficiently large n.

What does the set Ω(g(n)) actually represent?

g(n) must be slower than (or equal to) t(n) in terms of order of growth — Big-Omega gives a lower bound.

How does the growth-rate relationship in Ω(g(n)) contrast with O(g(n))?

In O(g(n)), g(n) must be faster (or equal); in Ω(g(n)), g(n) must be slower (or equal)

Big-O gives an upper bound (g grows at least as fast as t); Big-Omega gives a lower bound (g grows no faster than t).

What's the key inequality used to prove n³ ∈ Ω(n²)?

n³ ≥ n² for all n ≥ 0

Since n³ grows at least as fast as n² for every n ≥ 0, the inequality holds with no lower bound needed on n.

What values of c and n0 prove n³ ∈ Ω(n²)?

c = 1, n0 = 0

Since the inequality n³ ≥ n² holds for every n ≥ 0, we can pick the smallest possible constants: c = 1 and n0 = 0.

What does it mean for t(n) to be in Θ(g(n))?

c2·g(n) ≤ t(n) ≤ c1·g(n) for all n ≥ n0, for some positive constants c1, c2 and nonnegative integer n0

This is the formal definition of Big-Theta: t(n) is sandwiched between two constant multiples of g(n) for all sufficiently large n.

In c2·g(n) ≤ t(n) ≤ c1·g(n) for all n ≥ n0, how do c1, c2, and n0 work together?

c2 sets the lower bound and c1 sets the upper bound, both holding from the same n0 onward

Both bounds must hold using the same n0 — t(n) is bounded both above and below by positive constant multiples of g(n).

What does the set Θ(g(n)) actually represent?

All functions that have the same order of growth as g(n), up to a constant multiple, as n → ∞

Θ(g(n)) is the "tight bound" set — it combines both O(g(n)) and Ω(g(n)).

Every quadratic function an² + bn + c with a > 0 belongs to which Theta class?

Θ(n²)

The an² term dominates for large n, and with a>0 the function is both upper- and lower-bounded by constant multiples of n² — a tight bound.