Analysis of Algorithms 4
Analysis of Algorithms
1
+
+ c c
– Assignment 4
This assignment is due by 4:00pm on Wednesday March 1.
Proofs will be graded on both co
ectness and presentaAon. Clearly explain all of your steps. The
total number of marks is 40.
GLOBAL INSTRUCTIONS
❼ In QuesAons 1 - 4, when you are asked to prove a given statement, you may only use basic alge
a
and arithmeAc, and the definiAons of O(), Ω(), Θ(), o() and ω(). Do not use limits, statements about
the hierarchy of funcAons, or any of the properAes listed in the document Week5-Properties.pdf.
❼ The rules for QuesAon 5 are different. Make sure you read the quesAon carefully.
You can use the properAes of exponenAals and logarithms that were covered in the Week 2 Math Review
in any of your proofs. For example, here are some facts that might be helpful.
❼ For any a, b ∈ R and any c > 1, a < b if and only if logc(a) < logc(b)
❼ For any a, b, c ∈ R , a < b if and only if a < b
Questions
1. Using only the definiAons of O() and Ω(), prove the following.
(a) [2 marks] 3n4 + 7n2 + 6 ∈ O(n4)
(b) [3 marks] n3 − 8n2 ∈ Ω(n3)
(c) [3 marks] (2n)! ∈/ O(n!)
2. Using only the definiAon of Θ(), prove the following.
(a) [4 marks] log2(n10 + n + 2) ∈ Θ(log2(n))
(b) [3 marks] n3/4 ∈/ Θ(n)
Analysis of Algorithms
2
3. Using only the definiAons of o() and ω(), prove the following.
(a) [3 marks] n! ∈/ o(5n)
(b) [3 marks] 4n − 2n ∈ ω(3n)
4. Using only the definiAons of O(), o(), Ω(), ω() and Θ(), prove the following. Hints:
❼ Begin by clearly staAng what you are assuming, and what you need to prove.
❼ If you find yourself wriAng something like “Let M = 3M ” in your proof, then you are using two
different M ’s and they should have different names. You can use subscripts (M1, n1, M2,
n2, XXXXXXXXXXor primes (M ′, n′ , M ′′, n′′, XXXXXXXXXXto disAnguish between your
0 0
variables.
In these statements, f , g, h, f1, f2, g1 and g2 are all a
itrary funcAons that map Z+ → R+.
(a) [3 marks] If f1 ∈ O(g1) and f2 ∈ O(g2) then f1f2 ∈ O(g1g2)
(b) [3 marks] If f ∈ o(g), then f ∈/ Ω(g)
(c) [3 marks] If f1 ∈ ω(f2) and g ∈ Θ(h), then f1g ∈ ω(f2h).
5. In this quesAon, you will not use the definiAons of asymptoAc notaAon to prove the given
statements. Instead, you will use only basic arithmeAc and alge
a, and the list of facts given in
the final pages of this document. Every step in your proof must be jusAfied by referencing one of
these facts. Read the list carefully before you start working on your proofs!
In these statements, a and b are constants (i.e., they are not funcAons of n).
(a) [2 marks] Prove that for all a > 1 and b > 0, an + nb ∈ o(n!).
(b) [2 marks] Prove that for all a > 1 and b > 0, nb loga(n) ∈ ω(loga(n)).
(c) [2 marks] Prove that for all b > a > 1, nan ∈ o(bn). (Hint: construct a number c such that a < c
b.)
(d) [4 marks] Prove that for all a, b > 0, an + b ∈ Θ(n).
Analysis of Algorithms
3
QuesAon 5 Facts
Here are the statements that you can use to jusAfy your steps in QuesAon 5. Cite them by number: e.g.,
“By (1.6), . . .”
In these statements, a, b and c are constants (i.e., they are not funcAons of n), and f , g, h, f1, f2, g1 and g2
are funcAons that map Z+ → R+.
Group 1: the hierarchy summarized. For all constants a > 0 and b > 0: (1.1) if
a > 1, then 1 ∈ o(loga(n))
(1.2) if a > 1, then loga(n) ∈ o(nb)
(1.3) if a < b, then na ∈ o(nb) (1.4)
if b > 1, then na ∈ o(bn XXXXXXXXXXif 1 <
a < b, then an ∈ o(bn XXXXXXXXXXan ∈
o(n!)
Group 2: transitivity.
(2.1) if f ∈ O(g) and g ∈ O(h), then f ∈ O(h)
(2.2) if f ∈ Ω(g) and g ∈ Ω(h), then f ∈ Ω(h)
(2.3) if f ∈ o(g) and g ∈ o(h), then f ∈ o(h)
(2.4) if f ∈ ω(g) and g ∈ ω(h), then f ∈ ω(h)
Group 3: condiAonals and biconditionals.
(3.1) f ∈ Θ(g) if and only if f ∈ O(g) and f ∈ Ω(g XXXXXXXXXXf ∈
O(g) if and only if g ∈ Ω(f )
(3.3) f ∈ o(g) if and only if g ∈ ω(f ) (3.4)
if f ∈ o(g), then f ∈ O(g)
(3.5) if f ∈ ω(g), then f ∈ Ω(g)
(3.6) If f ∈ o(g), then f ∈/ Ω(g)
(3.7) If f ∈ ω(g), then f ∈/ O(g)
Analysis of Algorithms
4
Group 4: addition.
(4.1) if f ∈ O(h) and g ∈ O(h), then f + g ∈ O(h XXXXXXXXXXif f ∈
Ω(h), then f + g ∈ Ω(h)
(4.3) if f ∈ o(h) and g ∈ o(h), then f + g ∈ o(h XXXXXXXXXXif
f ∈ ω(h), then f + g ∈ ω(h)
Group 5: multiplication.
(5.1) for any constant c > 0, cf ∈ Θ(f )
(5.2) if f1 ∈ O(g1) and f2 ∈ O(g2) then f1f2 ∈ O(g1g XXXXXXXXXXif f1 ∈
Ω(g1) and f2 ∈ Ω(g2) then f1f2 ∈ Ω(g1g XXXXXXXXXXif f1 ∈ o(g1) and f2
∈ o(g2) then f1f2 ∈ o(g1g XXXXXXXXXXif f1 ∈ ω(g1) and f2 ∈ ω(g2)
then f1f2 ∈ ω(g1g2)
– Assignment 4
Question 5 Facts
Week 5 – Properties of Asymptotic Notation
This document contains a list of some useful properties of
asymptotic notation. You will be using an identical list in
Assignment 4.
You can use these properties to decide whether a given statement
involving asymptotic notation is true or false.
However, remember that if you are asked to prove a statement
from the definitions, you should use only the formal definitions of
asymptotic notation and not any of these properties (unless you
prove them!).
In these statements, a, b and c are constants (i.e., they are not
functions of n), and f , g , h, f1, f2, g1 and g2 are functions that
map Z+ → R+.
1 / 7
Week 5 – Properties of Asymptotic Notation
Group 1: the hierarchy summarized
For all constants a > 0 and b > 0:
(1.1) if a > 1, then 1 ∈ o(loga(n))
(1.2) if a > 1, then loga(n) ∈ o(nb)
(1.3) if a < b, then na ∈ o(nb)
(1.4) if b > 1, then na ∈ o(bn)
(1.5) if 1 < a < b, then an ∈ o(bn)
(1.6) an ∈ o(n!)
2 / 7
Week 5 – Properties of Asymptotic Notation
Group 2: transitivity
(2.1) if f ∈ O(g) and g ∈ O(h), then f ∈ O(h)
(compare with (x ≤ y) ∧ (y ≤ z) ⇒ (x ≤ z))
(2.2) if f ∈ Ω(g) and g ∈ Ω(h), then f ∈ Ω(h)
(compare with (x ≥ y) ∧ (y ≥ z) ⇒ (x ≥ z))
(2.3) if f ∈ o(g) and g ∈ o(h), then f ∈ o(h)
(compare with (x < y) ∧ (y < z) ⇒ (x < z))
(2.4) if f ∈ ω(g) and g ∈ ω(h), then f ∈ ω(h)
(compare with (x > y) ∧ (y > z) ⇒ (x > z))
3 / 7
Week 5 – Properties of Asymptotic Notation
Group 3: conditionals and biconditionals
(3.1) f ∈ Θ(g) if and only if f ∈ O(g) and f ∈ Ω(g)
(compare with (x = y) ⇔ ((x ≤ y) ∧ (x ≥ y)))
(3.2) f ∈ O(g) if and only if g ∈ Ω(f )
(compare with (x ≤ y) ⇔ (y ≥ x))
(3.3) f ∈ o(g) if and only if g ∈ ω(f )
(compare with (x < y) ⇔ (y > x))
(3.4) if f ∈ o(g), then f ∈ O(g)
(compare with (x < y) ⇒ (x ≤ y))
(3.5) if f ∈ ω(g), then f ∈ Ω(g)
(compare with (x > y) ⇒ (x ≥ y))
4 / 7
Week 5 – Properties of Asymptotic Notation
Group 3: conditionals and biconditionals (cont’d)
(3.6) If f ∈ o(g), then f /∈ Ω(g)
(compare with x < y ⇒ x ̸≥ y)
(3.7) If f ∈ ω(g), then f /∈ O(g)
(compare with x > y ⇒ x ̸≤ y)
Note that the converses of (3.6) and (3.7) are not true fo
functions, even if their counterparts are true for real numbers!
5 / 7
Week 5 – Properties of Asymptotic Notation
Group 4: addition
(4.1) if f ∈ O(h) and g ∈ O(h), then f + g ∈ O(h)
(4.2) if f ∈ Ω(h), then f + g ∈ Ω(h)
(4.3) if f ∈ o(h) and g ∈ o(h), then f + g ∈ o(h)
(4.4) if f ∈ ω(h), then f + g ∈ ω(h)
6 / 7
Week 5 – Properties of Asymptotic Notation
Group 5: multiplication
(5.1) for any constant c > 0, cf ∈ Θ(f )
(5.2) if f1 ∈ O(g1) and f2 ∈ O(g2) then f1f2 ∈ O(g1g2)
(5.3) if f1 ∈ Ω(g1) and f2 ∈ Ω(g2) then f1f2 ∈ Ω(g1g2)
(5.4) if f1 ∈ o(g1) and f2 ∈ o(g2) then f1f2 ∈ o(g1g2)
(5.5) if f1 ∈ ω(g1) and f2 ∈ ω(g2) then f1f2 ∈ ω(g1g2)
7 / 7
Week 5 – Extra Exercises
EXERCISE 1. Prove each of the following, using the definition of
O().
(a) Show that 7n + 12 ∈ O(n)
(b) Show that 8n4 + n + 5 ∈ O(n4).
(c) Show that n2 − 5n /∈ O(n)
(d) Show that 3n3 − n2 /∈ O(n2).
1 / 28
Week 5 – Extra Exercises
EXERCISE 1. Prove each of the following, using the definition of
O().
(a) Show that 7n + 12 ∈ O(n)
Solution
Let M = 19 and n0 = 1. We will show that for all n > 1,
7n + 12 < 19n.
Let n > 1 be a
itrary. Then
7n + 12 < 7n + 12n = 19n,
as needed.
2 / 28
Week 5 – Extra Exercises
(b) Show that 8n4 + n + 5 ∈ O(n4).
Solution
Let M = 14 and n0 = 1. We claim that for all n > 1,
8n4 + n + 5 < 14n4.
Let n > 1 be a
itrary. Then n4 > n > 1, and so
8n4 + n + 5 < 8n4 + n4 + 5n4 = 14n4,
as needed.
3 / 28
Week 5 – Extra Exercises
(c) Show that n2 − 5n /∈ O(n)
Solution
Let M > 0 and n0 > 0 be a
itrary. We will find n > n0 such
that n2 − 5n > Mn.
Let n = max {n0 + 1, 11, 2M}. Then n > n0, and n > 2M,
which implies that 12n > M. Finally, n > 10, which implies
that 1n
1
10 .
Now,
n2 − 5n = n2
(
1− 5
n
)
n2
(
1− 5
10
)
=
1
2
n2 > Mn,
as needed.
4 / 28
Week 5 – Extra Exercises
(d) Show that 3n3 − n2 /∈ O(n2).
Solution
Let M > 0 and n0 > 0 be a
itrary. We will find n > n0 so
that 3n3 − n2 > n2.
Let n = max {n0 + 1,M + 1}. Then n > n0 and n > M. Also,
n > 1, which implies that n3 > n2. We have
3n3 − n2 = n3
(
3− 1
n
)
n3 (3− 1) = 2n3 > n3 > Mn2,
as needed.
5 / 28
Week 5 – Extra Exercises
EXERCISE 2. Prove each of the following using the definition of
O().
(a) Show that 4n ∈ O(n!)
(b) Show that 4n + 2n ∈ O(n!)
(c) Show that n! ∈ O(nn)
(d) Show that 3n /∈ O(2n)
6 / 28
Week 5 – Extra Exercises
EXERCISE 2. Prove each of the following using the definition of
O().
(a) Show that 4n ∈ O(n!)
Solution
Let M = 43 and n0 = 3. We will show that for all n > 3,
4n < 43n!.
Let n > 3 be a
itrary. Then n! is a product of at least 4
factors:
n!