Great Deal! Get Instant $10 FREE in Account on First Order + 10% Cashback on Every Order Order Now

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 correctness and presentaAon....

1 answer below »
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!
Answered 1 days After Feb 26, 2023

Solution

Vikas answered on Feb 28 2023
38 Votes
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, n3/4 cannot be both ≤ c2n and ≥ c1n for all.
PART 3: Using only the definitions of o() and ω(), prove the following.
(a) n! ∈/ o(5n)
We will prove this by contradiction. Suppose that n! ∈ o(5n). Then there exists a...
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here