submit assignment and support file
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 correctness 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 algebra 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 be 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 arbitrary 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 algebra, 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 b b a y by = 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 b logb an = n logb a logb a = logc a logc b logb(1/a) = − logb a logb a = 1 loga b 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, break 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 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,="" break="" 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="">