"Big-Oh", "Big-Omega", and "Big-Theta": Properties and Rules

Outline Big-Oh rules Examples
“Big-Oh”, “Big-Omega”, and “Big-Theta”:

Properties and Rules
Lecturer: Georgy Gimel’farb
COMPSCI 220 Algorithms and Data Structures
1 / 14
1 Big-Oh rules
Scaling
Transitivity
Rule of sums
Rule of products
Limit rule
2 Examples
2 / 14
Scaling
Big-Oh: Scaling
Scaling (Lemma 1.15)

For all constant factors c > 0, the function cf (n) is O(f (n)),
or in shorthand notation cf is O(f ).
The proof: cf (n) < (c + ε)f (n) holds for all n > 0 and ε > 0.
• Constant factors are ignored.
• Only the powers and functions of n should be exploited
It is this ignoring of constant factors that motivates for such a
notation! In particular, f is O(f ).

50n ∈ O(n) 0.05n ∈ O(n)
Examples:
50, 000, 000n ∈ O(n) 0.0000005n ∈ O(n)
3 / 14
Scaling
Big-Oh: Scaling


50n ∈ O(n) 0.05n ∈ O(n)
Examples:
50, 000, 000n ∈ O(n) 0.0000005n ∈ O(n)
3 / 14
Scaling
Big-Oh: Scaling


50n ∈ O(n) 0.05n ∈ O(n)
Examples:
50, 000, 000n ∈ O(n) 0.0000005n ∈ O(n)
3 / 14
Scaling
Big-Oh: Scaling


50n ∈ O(n) 0.05n ∈ O(n)
Examples:
50, 000, 000n ∈ O(n) 0.0000005n ∈ O(n)
3 / 14
Transitivity
Big-Oh: Transitivity
Transitivity (Lemma 1.16)

If h is O(g) and g is O(f ), then h is O(f ).
The proof:
◦ h(n) ≤ c1 g(n) for n > n1 ; c1 > 0, because h ∈ O(g).
• g(n) ≤ c2 f (n) for n > n2 ; c2 > 0, because g ∈ O(f ).
→ Substituting the second inequality (•) into the first inequality
(◦) leads to the inequality
h(n) ≤ c1 c2 f (n) for n > max{n1 , n2 }

|{z} | {z }
c; c>0 n0
proving the transitivity rule.
4 / 14
Transitivity
Transitivity (Lemma 1.16)

If h is O(g) and g is O(f ), then h is O(f ).
The proof:
◦ h(n) ≤ c1 g(n) for n > n1 ; c1 > 0, because h ∈ O(g).
• g(n) ≤ c2 f (n) for n > n2 ; c2 > 0, because g ∈ O(f ).
→ Substituting the second inequality (•) into the first inequality
(◦) leads to the inequality
h(n) ≤ c1 c2 f (n) for n > max{n1 , n2 }

|{z} | {z }
c; c>0 n0
proving the transitivity rule.
4 / 14
Transitivity
Informal meaning of the transitivity rule:

If function h(n) grows at most as fast as g(n),
which grows at most as fast as f (n),
then h(n) grows at most as fast as f (n).
Examples:
• If h ∈ O(g) and g ∈ O(n2 ), then h ∈ O(n2 ).
• If log10 n ∈ O(n0.01 ) and n0.01 ∈ O(n), then log10 n ∈ O(n).
• If n50 ∈ O(2n ) and 2n ∈ O(3n ), then n50 ∈ O(3n ).
5 / 14
Transitivity

Examples:
5 / 14
Transitivity

Examples:
5 / 14
Transitivity

Examples:
5 / 14
Rule of sums
Big-Oh: Rule of Sums
Rule-of-sums (Lemma 1.17)

If g1 ∈ O(f1 ) and g2 ∈ O(f2 ), then g1 + g2 ∈ O(max{f1 , f2 }).
The proof:
◦ g1 (n) ≤ c1 f1 (n) for n > n1 , because g1 ∈ O(f1 ).
• g2 (n) ≤ c2 f2 (n) for n > n2 , because g2 ∈ O(f2 ).
→ Summing the inequalities (◦) and (•) leads to the inequality
g1 (n) + g2 (n) ≤ c1 f1 (n) + c2 f2 (n)
≤ max{c1 , c2 } (f1 (n) + f2 (n))
≤ 2 · max{c1 , c2 } · max {f1 (n), f2 (n)}
| {z }
c; c>0
for n > max{n1 , n2 }, proving the rule of sums.

| {z }
n0
6 / 14
Rule of sums

The proof:
g1 (n) + g2 (n) ≤ c1 f1 (n) + c2 f2 (n)
≤ max{c1 , c2 } (f1 (n) + f2 (n))
≤ 2 · max{c1 , c2 } · max {f1 (n), f2 (n)}
| {z }
c; c>0

| {z }
n0
6 / 14
Rule of sums

The proof:
g1 (n) + g2 (n) ≤ c1 f1 (n) + c2 f2 (n)
≤ max{c1 , c2 } (f1 (n) + f2 (n))
≤ 2 · max{c1 , c2 } · max {f1 (n), f2 (n)}
| {z }
c; c>0

| {z }
n0
6 / 14
Rule of sums
Informal meaning of the rule of sums:

The sum of functions grows as its fastest-growing term.
Therefore,
• If g ∈ O(f ) and h ∈ O(f ), then g + h ∈ O(f ).
• If g ∈ O(f ), then g + f ∈ O(f ).
• If g(n) = a0 + a1 n + . . . + ak nk (a polynomial of degree k),
then g(n) ∈ O(nk ).
Examples:
and g ∈ O(n2 ), then g + h ∈ O(n2 )

(
If h ∈ O(n)
If h ∈ O(n log n) and g ∈ O(n), then g + h ∈ O(n log n)
7 / 14
Rule of sums

T (n)
f2 (n)
max{f1 , f2 }
g1 + g2
f1 (n)
g2 (n) = O(f2 (n))
g1 (n) = O(f1 (n))
8 / 14
Rule of products
Big-Oh: Rule of Products
Rule-of-products (Lemma 1.18)

If g1 ∈ O(f1 ) and g2 ∈ O(f2 ), then g1 g2 ∈ O(f1 f2 ).
The proof:
→ Multiplying the inequalities (◦) and (•) leads to the inequality
g1 (n)g2 (n) ≤ c1 c2 f1 (n)f2 (n) for n > max{n1 , n2 }

|{z} | {z }
c; c>0 n0
proving the rule of products.
9 / 14
Rule of products

The proof:

|{z} | {z }
c; c>0 n0
9 / 14
Rule of products

The proof:

|{z} | {z }
c; c>0 n0
9 / 14
Rule of products
Informal meaning of the rule of products:

The product of upper bounds of functions gives an upper bound
for the product of the functions.
Therefore,
• If g ∈ O(f ) and h ∈ O(f ), then gh ∈ O(f 2 ).
• If g ∈ O(f ) and h ∈ O(f k ), then gh ∈ O(f k+1 ).
• If g ∈ O(f ) and h(n) is a given function, then gh ∈ O(f h).
Examples:
• If h ∈ O(n) and g ∈ O(n2 ), then gh ∈ O(n3 ).
• If h ∈ O(log n) and g ∈ O(n), then gh ∈ O(n log n).
10 / 14
Limit rule
Big-Oh: The Limit Rule

f (n)
Suppose the ratio’s limit lim = L exists (may be infinite, ∞).
n→∞ g(n)

 if L = 0 then f ∈ O(g)
Then if 0 < L < ∞ then f ∈ Θ(g)
if L = ∞ then f ∈ Ω(g)

When f and g are positive and differentiable functions for x > 0, but
lim f (x) = lim g(x) = ∞ or lim f (x) = lim g(x) = 0, the limit L
x→∞ x→∞ x→∞ x→∞
can be computed using the standard L’Hopital rule of calculus:
f (x) f 0 (x)
lim = lim 0
x→∞ g(x) x→∞ g (x)
dz(x)
where z 0 (x) ≡ dx denotes the first derivative of the function z(x).
11 / 14
Example 1.22 (Textbook)
Prove that exponential functions grow faster than powers:

nk is O(bn ) for all b > 1, n > 1, and k ≥ 0.
The proof – either by induction, or what is simpler,

by the limit rule using successive (k + 1 times) differentiation of
f (x) = xk and g(x) = bx by x:
• Derivatives of f (x) = xk by x for k ≥ 0:
dxk d 2 xk
dn = kxk−1 ; dx2
= k(k − 1)xk−2 ; . . .
dk xk dk+1 xk
dxk
= k(k − 1) · · · 2 · 1 = k!; dxk+1
=0
12 / 14


dxk d 2 xk
dn = kxk−1 ; dx2
= k(k − 1)xk−2 ; . . .
dk xk dk+1 xk
dxk
= k(k − 1) · · · 2 · 1 = k!; dxk+1
=0
12 / 14


dxk d 2 xk
dn = kxk−1 ; dx2
= k(k − 1)xk−2 ; . . .
dk xk dk+1 xk
dxk
= k(k − 1) · · · 2 · 1 = k!; dxk+1
=0
12 / 14
• Derivatives of g(x) = bx by x:
dbx d2 bx
dx = bx ln b; dx2
= bx (ln b)2 ; ...
dk bx dk+1 bx
dxk
= bx (ln b)k ; dxk+1
= bx (ln b)k+1
• Therefore, by the L’Hopital rule, the limit of the ratio
nk 0
lim = lim n =0
n→∞ bn n→∞ b (ln b)k+1
for b > 1, proving that nk ∈ O(bn ) for all b > 1, n > 1, and
k ≥ 0.
13 / 14
• Derivatives of g(x) = bx by x:
dbx d2 bx
dx = bx ln b; dx2
= bx (ln b)2 ; ...
dk bx dk+1 bx
dxk
= bx (ln b)k ; dxk+1
= bx (ln b)k+1
• Therefore, by the L’Hopital rule, the limit of the ratio
nk 0
lim = lim n =0
n→∞ bn n→∞ b (ln b)k+1
for b > 1, proving that nk ∈ O(bn ) for all b > 1, n > 1, and
k ≥ 0.
13 / 14
Prove that logarithmic functions grow slower than powers:

logb n is O(nk ) for all b > 1, n > 1, and k > 0.
The proof:
k
• The first derivative of f (x) = xk by x is dx
dx = kx
k−1 .
• The first derivative of g(x) = logb x by x is d log

dx
bx 1
= x ln b.
• By the limit rule, lim fg(n)
(n)
= lim (k ln b)nk = ∞ for n > 1,
n→∞ n→∞
b > 1, and k ≥ 0, proving nk ∈ Ω(logb n), i.e. logb n ∈ O(nk ).
As a result, log n ∈ O(n); n log n ∈ O(n2 ), and log n ∈ O(n0.0001 ).
logb n is O(log n) for all b > 1 because logb n = logb a × loga n
14 / 14

The proof:
k
dx = kx
k−1 .

dx
bx 1
= x ln b.
(n)
n→∞ n→∞
14 / 14

The proof:
k
dx = kx
k−1 .

dx
bx 1
= x ln b.
(n)
n→∞ n→∞
14 / 14

The proof:
k
dx = kx
k−1 .

dx
bx 1
= x ln b.
(n)
n→∞ n→∞
14 / 14

The proof:
k
dx = kx
k−1 .

dx
bx 1
= x ln b.
(n)
n→∞ n→∞
14 / 14

The proof:
k
dx = kx
k−1 .

dx
bx 1
= x ln b.
(n)
n→∞ n→∞
14 / 14

"Big-Oh", "Big-Omega", and "Big-Theta": Properties and Rules

Uploaded by

Copyright:

Available Formats

"Big-Oh", "Big-Omega", and "Big-Theta": Properties and Rules

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

"Big-Oh", "Big-Omega", and "Big-Theta": Properties and Rules

Uploaded by

Copyright:

Available Formats

Outline Big-Oh rules Examples

“Big-Oh”, “Big-Omega”, and “Big-Theta”:

Lecturer: Georgy Gimel’farb

COMPSCI 220 Algorithms and Data Structures

Scaling (Lemma 1.15)

Scaling (Lemma 1.15)

Scaling (Lemma 1.15)

Scaling (Lemma 1.15)

Transitivity (Lemma 1.16)

h(n) ≤ c1 c2 f (n) for n > max{n1 , n2 }

proving the transitivity rule.

Transitivity (Lemma 1.16)

h(n) ≤ c1 c2 f (n) for n > max{n1 , n2 }

proving the transitivity rule.

Informal meaning of the transitivity rule:

• If log10 n ∈ O(n0.01 ) and n0.01 ∈ O(n), then log10 n ∈ O(n).

• If n50 ∈ O(2n ) and 2n ∈ O(3n ), then n50 ∈ O(3n ).

Informal meaning of the transitivity rule:

• If log10 n ∈ O(n0.01 ) and n0.01 ∈ O(n), then log10 n ∈ O(n).

• If n50 ∈ O(2n ) and 2n ∈ O(3n ), then n50 ∈ O(3n ).

Informal meaning of the transitivity rule:

• If log10 n ∈ O(n0.01 ) and n0.01 ∈ O(n), then log10 n ∈ O(n).

• If n50 ∈ O(2n ) and 2n ∈ O(3n ), then n50 ∈ O(3n ).

Informal meaning of the transitivity rule:

• If log10 n ∈ O(n0.01 ) and n0.01 ∈ O(n), then log10 n ∈ O(n).

• If n50 ∈ O(2n ) and 2n ∈ O(3n ), then n50 ∈ O(3n ).

Big-Oh: Rule of Sums

Rule-of-sums (Lemma 1.17)

for n > max{n1 , n2 }, proving the rule of sums.

Big-Oh: Rule of Sums

Rule-of-sums (Lemma 1.17)

for n > max{n1 , n2 }, proving the rule of sums.

Big-Oh: Rule of Sums

Rule-of-sums (Lemma 1.17)

for n > max{n1 , n2 }, proving the rule of sums.

Big-Oh: Rule of Sums

Informal meaning of the rule of sums:

and g ∈ O(n2 ), then g + h ∈ O(n2 )

Big-Oh: Rule of Sums

g1 (n) = O(f1 (n))

Big-Oh: Rule of Products

Rule-of-products (Lemma 1.18)

g1 (n)g2 (n) ≤ c1 c2 f1 (n)f2 (n) for n > max{n1 , n2 }

proving the rule of products.

Big-Oh: Rule of Products

Rule-of-products (Lemma 1.18)

g1 (n)g2 (n) ≤ c1 c2 f1 (n)f2 (n) for n > max{n1 , n2 }

proving the rule of products.

Big-Oh: Rule of Products

Rule-of-products (Lemma 1.18)

g1 (n)g2 (n) ≤ c1 c2 f1 (n)f2 (n) for n > max{n1 , n2 }

proving the rule of products.

Big-Oh: Rule of Products

Informal meaning of the rule of products:

Big-Oh: The Limit Rule

Example 1.22 (Textbook)

Prove that exponential functions grow faster than powers:

The proof – either by induction, or what is simpler,

Example 1.22 (Textbook)