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 correctness 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 algebra
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 log
c
(a) < log
c
(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, . . .) or primes (M ′, n′ , M ′′, n′′, . . .) to disAnguish between your
0 0
variables.
In these statements, f, g, h, f1, f2, g1 and g2 are all arbitrary 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 algebra, 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 log
a
(n) ∈ ω(log
a
(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(log
a
(n))
(1.2) if a > 1, then log
a
(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!)
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) (3.2) f ∈
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) (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)
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)