Assignment covers asymptotic notation and proofsAnalysis of Algorithms 4 Analysis of Algorithms 1 +...

Question

Assignment covers asymptotic notation and proofsAnalysis 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 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  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  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  1, then na ∈ o(bn) (1.5) if 1  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) 	– 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  1, then na ∈ o(bn) (1.5) if 1  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  x)) (3.4) if f ∈ o(g), then f ∈ O(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) Note that the converses of (3.6) and (3.7) are not true for 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  1 be arbitrary. Then 7n + 12  1, 8n4 + n + 5  1 be arbitrary. Then n4 > n > 1, and so 8n4 + n + 5  0 and n0 > 0 be arbitrary. 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  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 arbitrary. 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  3 be arbitrary. Then n! is a product of at least 4 factors: n!

Vikas · Accepted Answer

Assignment
PART 1: Using only the definitions of O() and Ω(), prove the following.
(a) 3n4 + 7n2 + 6 ∈ O(n4)
We need to find constants c and n0 such that 3n4 + 7n2 + 6 ≤ cn4 for all n ≥ n0.
Let c = 4 and n0 = 1. Then, for all n ≥ n0:
3n4 + 7n2 + 6 ≤ 3n4 + 7n4 + 6n4 (since n2 ≤ n4 for all n ≥ 1) = 16n4 ≤ 4n4
Therefore, 3n4 + 7n2 + 6 ∈ O(n4).
(b) n3 − 8n2 ∈ Ω(n3)
We need to find constants c and n0 such that n3 − 8n2 ≥ cn3 for all n ≥ n0.
Let c = 1/2 and n0 = 8. Then, for all n ≥ n0:
n3 − 8n2 ≥ n3/2 (since 8n2 ≤ n3/2 for all n ≥ 8) ≥ (1/2)n3
Therefore, n3 − 8n2 ∈ Ω(n3).
(c) (2n)! ∈/ O(n!)
We will prove this by contradiction. Suppose that (2n)! ∈ O(n!). Then there exist constants c and n0 such that (2n)! ≤ cn! for all n ≥ n0. But we know that:
(2n)! = (2n)(2n−1)(2n−2)...(n+1)n(n−1)...(2)(1) ≥ (2n)(n+1)n(n−1)...(2)(1) = (2n)!
This is a contradiction, since (2n)! cannot be both ≤ cn! and ≥ (2n)! for all n ≥ n0. Therefore, (2n)! ∈/ O(n!).
PART 2: Using only the definition of Θ(), prove the following.
Using only the definition of Θ(), prove the following.
(a) log2(n10 + n + 2) ∈ Θ(log2(n))
We need to find constants c1, c2, and n0 such that c1log2(n) ≤ log2(n10 + n + 2) ≤ c2log2(n) for all n ≥ n0.
For the upper bound, let c2 = 11 and n0 = 1. Then, for all n ≥ n0:
log2(n10 + n + 2) ≤ log2(11n10) = log2(11) + log2(n10) ≤ 12log2(n)
For the lower bound, let c1 = 1 and n0 = 1. Then, for all n ≥ n0:
log2(n10 + n + 2) ≥ log2(n10) = 10log2(n)
Therefore, log2(n10 + n + 2) ∈ Θ(log2(n)).
(b) n3/4 ∈/ Θ(n)
We will prove this by contradiction. Suppose that n3/4 ∈ Θ(n). Then there exist constants c1, c2, and n0 such that c1n ≤ n3/4 ≤ c2n for all n ≥ n0. But we know that:
n3/4 ≥ n/2 (since (n/2)4 ≤ n3 for all n ≥ 1)
Therefore,

Analysis of Algorithms 4Analysis of Algorithms1++ c c– Assignment 4 This assignment is due by 4:00pm on Wednesday March 1. Proofs will be graded on both correctness and presentaAon....

Answer To: Analysis of Algorithms 4Analysis of Algorithms1++ c c– Assignment 4 This assignment is...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment