COMP 2080 Winter 2022 – Assignment 4
This assignment is due by 11:59pm on Wednesday March 9.
Submission instructions. Your assignment will be submitted in Crowdmark and not in UM
Learn.
Proofs will be graded on both co
ectness and presentation. Clearly explain all of your steps.
GLOBAL INSTRUCTIONS
• In Questions 1 - 4, when you are asked to prove a given statement, you may only use basic
alge
a and arithmetic, and the definitions of O(), Ω(), Θ(), o() and ω(). Do not use limits,
statements about the hierarchy of functions, or any of the properties listed in the document
Properties and Limits that is posted under Lectures - Week 5.
• The rules for Question 5 are different. Make sure you read the question carefully.
You can use the properties of exponentials and logarithms that were covered in Math Review 5,
posted under Lectures - Week 2, in any of your proofs. For example, here are some facts that might
e helpful.
• For all x > 0 and y > 1, ylogy(x) = x and logy(yx) = x
• For all x > 0, y > 0 and z > 1, logz(xy) = logz(x) + logz(y)
• For all x > 0, y > 0 and z > 1, logz(xy) = y logz(x)
• For all x > 0, y > 0 and z > 1, x < y if and only if logz(x) < logz(y).
• For all x > 0, y > 0 and z > 0, x < y if and only if xz < yz
• For all x > 0, y > 0 and z > 0, xzyz = (xy)z
• For all x > 0, y > 0 and z > 0, zxzy = zx+y
Questions
1. (a) [4 marks] Prove that log2(n
2 + 1) ∈ O(log2(n))
(b) [4 marks] Prove that 12n
4 − 10n3 − n ∈ Ω(n4)
2. (a) [4 marks] Prove that (2n)! /∈ Θ(n!)
(b) [4 marks] Prove that n3 − 4n2 /∈ o(n3)
1
3. The cost functions for the three algorithms you analyzed in Assignment 3 Question 4 are
f1(n) =
3
2
n2 +
5
2
n
f2(n) = n
2 + 5n
f3(n) = 6n
(a) [4 marks] Prove that f1(n) ∈ Θ(f2(n)).
(b) [4 marks] Prove that f2(n) ∈ ω(f3(n)).
4. Let f and g be a
itrary functions such that f, g : Z+ → R+. That is, f(n) is defined for all
positive integers n, and f(n) > 0 for all such n, and the same is true of g.
(a) [5 marks] Prove that if g ∈ o(f), then f − g ∈ Θ(f).
(b) [5 marks] Prove that if f ∈ Θ(g) and h ∈ o(f), then h ∈ o(g).
5. In this question, you will not use the definitions of asymptotic notation to prove the given
statements. Instead, you will use only basic arithmetic and alge
a, and the list of facts given
in the final pages of this document. Every step in your proof must be justified by referencing
one of these facts. Read the list carefully before you start working on your proofs!
In these statements, a, b and c are constants (i.e., they are not functions of n).
(a) [2 marks] Prove that for all a, b > 1, if a < b, then for all c > 0, an + nc ∈ o(bn).
(b) [2 marks] Prove that for all c > 0, nc ∈ ω((log n)2).
(c) [2 marks] Prove that for all c > 0, nc · 2n ∈ o(3n)
(d) [4 marks] Prove that for all a > 0, n2 + an ∈ Θ(n2).
(e) [4 marks] Prove that 3n − 2n ∈ ω(2n). For this proof, you can also use the statements
given in Question 4 parts (a) and (b)
2
Question 5 Facts
Here are the statements that you can use to justify your steps in Question 5. Cite them by number:
e.g., “By (1.6), . . .”
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+.
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!)
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: conditionals 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)
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)
3
(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)
4
2022 - Math Review 6 - Exponents, Logs, Floor, Ceiling.key
MATH REVIEW!
EXPONENTS, LOGARITHMS, FLOOR, CEILING
(even I hate myself for using this)
Lecture Outline
1. Exponents and Logarithms
2. Floors and Ceilings
2
Exponent Identities
For all real , and all real , we have:
1.
2.
3.
4.
5.
6.
a > 0 m, n
a0 = 1
a1 = a
a−1 = 1/a
(am)n = amn
(am)n = (an)m
aman = am+n
3
Logarithm Definition
For positive real numbers , and ,
the logarithm of with respect to base is defined as the
exponent by which must be raised to yield
In other words, it is the value of in the following
equation:
It is written as
Simple values:
a, b b ≠ 1
a
a
y
y = a
logb a
logb b = 1
logb 1 = 0
4
Logarithm Identities
For all real , , and , we have:
1.
2.
3.
4.
5.
6.
a > 0 b > 0 c > 0 n
a = blogb a
logc(ab) = logc a + logc
logb an = n logb a
logb a =
logc a
logc
logb(1/a) = − logb a
logb a =
1
loga
5
Lecture Outline
1. Exponents and Logarithms
2. Floors and Ceilings
6
For any real number
the floor of , written as , is the largest
integer that is less than or equal to
the ceiling of , written as , is the smallest
integer that is greater than or equal to
Based on this definition, we can see:
x
x ⌊x⌋
x
x ⌈x⌉
x
x − 1 < ⌊x⌋ ≤ x ≤ ⌈x⌉ < x + 1
Definitions 7
1. If is an integer, then
2. and
3. For any integer k:
4. For any integer k:
5. For any integer k:
and
(to prove these,
eak into even and odd cases, apply above facts)
6. for integers : and
x ⌊x⌋ = ⌈x⌉ = x
−⌊x⌋ = ⌈−x⌉ −⌈x⌉ = ⌊−x⌋
k + ⌊x/y⌋ = ⌊k + (x/y)⌋
k + ⌈x/y⌉ = ⌈k + (x/y)⌉
⌊(k + 1)/2⌋ = ⌈k /2⌉ ⌈(k − 1)/2⌉ = ⌊k /2⌋
a, b ⌊ ⌊x/a⌋b ⌋ = ⌊ xab ⌋ ⌈ ⌈x/a⌉b ⌉ = ⌈ xab ⌉
Some Useful Facts about Floors/Ceilings 8