Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP 2080 Winter 2022 – Assignment 4 Solutions


Questions

1.  (a)  [4 marks] Prove that log2(n2 + 1) ∈ O(log2(n))


Solution


(1) Let M = 3 and n0 = 2. We will show that for all n > 2, log2(n2 + 1) ≤ 3log2(n).

(2) Let n > 2 be arbitrary. Then n2 > 1, and log2(n) > log2(2) = 1.


(3) Using (2), we have

log2(n2 + 1)   < log2(n2 + n2)

=   log2(2n2)

=   log2(2) + log2(n2)

=   1 + 2log2(n)

< log2(n) + 2log2(n) = 3log2(n),

as needed.


(b)  [4 marks] Prove that n4 − 10n3 − n ∈ Ω(n4)


Solution

(1) Let M = and n0 = 80. We will show that for all n > 80, n4 − 10n3 − n ≥ n4 .

(2) Let n > 80 be arbitrary. Then < , which implies that < and < < .

(3) Observe that

n4 − 10n3 − n   = n4 1 −

> n4 1 − by (2)

=     n4 ,


as needed.


2.  (a)  [4 marks] Prove that (2n)! Θ(n!)

Solution

(1) To show that (2n)! Θ(n!), it suffices to show that ∀M1  > 0, ∀M2  > 0, ∀n0  > 0, ∃n > n0  such that either (2n)! < M1n! or (2n)! > M2n!.

(2) Let M1   > 0, M2   > 0 and n0   > 0 be arbitrary.   We will find n  > n0  such that (2n)! > M2n!.

(3) Let n = max{n0 + 1,M2 + 1}.  Then n > n0  > 0, and n > M2, which implies that 2n > M2 .

(4) Since n > 0 from (3), by the definition of the factorial function,

(2n)! = (2n)(2n − 1)...(n + 1) n!.

{z

n terms

There is at least one factor in the product (2n)(2n − 1)...(n + 1), and all of the factors in this product are positive integers. Consequently, (2n)(2n − 1)...(n + 1) ≥ 2n.

(5) Now,

(2n)!   =   (2n)(2n − 1)...(n + 1)n!

≥   (2n)n!   by (4)

>   M2n!   by (3)

which is what we needed to prove.

(b)  [4 marks] Prove that n3 − 4n2 o(n3)

Solution

(1) It suffices to show that ∃M > 0, ∀n0 > 0, ∃n > n0 , n3 − 4n2 > Mn3 .



(2) Let M  = , and let n0 n3 − 4n2 > n3 .

(3) Let n = max{n0 + 1, 9}. thus < .

(4) Using (3), we find








as needed.


> 0 be arbitrary.   We will construct n  > n0  such that


Then n > n0, and n > 8, which implies that < and



n3 − 4n2    =   n3 1 −

>   n3 1 −

=     n3 ,


3. The cost functions for the three algorithms you analyzed in Assignment 3 Question 4 are

f1(n)   =     n2 + n

f2(n)   =   n2 + 5n

f3(n)   =   6n

(a)  [4 marks] Prove that f1(n) ∈ Θ(f2(n)).

Solution

(1) Let M1  = , M2  = 4, and n0  = 1.  Let n > 1 be arbitrary.  We will show that n2 + 5n n2 + n and n2 + n ≤ 4 n2 + 5n .

(2) Since n > 1, we see that n2 > n, and therefore

n2 + 5n < n2 + 5n2 = 6n2 .

(3) Since n > 1, we also know that n > 0. Using (2), we find that



4 n2 + 5n







< 4 6n2

=     n2

< n2 + n.



(4) As noted in (2), n2 > n. Since n > 1, we have that 5n > 0. Thus

n2 + n   < n2 + n2

=   4n2

< 4 n2 + 5n .

This completes the proof.

(b)  [4 marks] Prove that f2(n) ∈ ω(f3(n)).

Solution

(1) Let M > 0 be arbitrary. We will find n0 > 0 such that for all n > n0 , n2+5n ≥ M(6n).

(2) Let n0 = 6M, and let n > n0 be arbitrary. Then n > n0 > 0 and n > 6M .

(3) Since n > 0, we have 5n > 0, and therefore

n2 + 5n   >   n2

=   n · n

>   6Mn,    by (2).


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).

Solution

(1) Assume that g ∈ o(f).  Then ∀M > 0, ∃n0  > 0, ∀n > n0 , g(n) ≤ Mf(n).  We will show that f − g ∈ Θ(f).

(2) Let M1 = and M2 = 1. We will find n0 > 0 such that for all n > n0 ,

(a) f(n)   ≤   f(n) − g(n),

(b)   f(n) − g(n)   ≤   f(n).

(3) Using (1), choose n0  such that for all n > n0 , g(n) ≤ f(n).

(4) Let n > n0 be arbitrary. Then, by the choice of n0 , g(n) ≤ f(n), which implies that

1             1

f(n) − g(n) ≥ f(n) − f(n) = f(n).

This proves statement (a).

(5) By assumption, g is a positive function. That is, g(n) > 0. Consequently, f(n) − g(n) < f(n).

This proves statement (b).

(b)  [5 marks] Prove that if f ∈ Θ(g) and h ∈ o(f), then h ∈ o(g).

Solution

(1) Assume that f ∈ Θ(g) and h ∈ o(f). We will show that h ∈ o(g).

(2) Let M > 0 be arbitrary. We will find n0 > 0 such that for all n > n0 , h(n) ≤ Mg(n).

(3) By (1), f ∈ Θ(g). Choose M1 > 0 and n1 > 0 such that for all n > n1 , f(n) ≤ M1g(n).

(4) Also by (1), h ∈ o(f). Choose n2 > 0 such that for all n > n2 , h(n) ≤ f(n).

(5) Let n0 = n1 + n2, and let n > n0 be arbitrary. We will show that h(n) ≤ Mg(n).

(6) From (5), n > n1 and n > n2. Using (3), we have f(n) ≤ M1g(n). Using (4), we have

M              M

h(n) ≤ f(n) ≤ (M1g(n)) = Mg(n),

as needed.


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 ).

Solution


(1) Let a,b > 1 be arbitrary, and assume that a < b. Let c > 0 be arbitrary. We claim that an + nc ∈ o(bn ).

(2) By (1.5), an ∈ o(bn ).

(3) By (1.4), nc ∈ o(bn ).

(4) By (4.3) applied to (2) and (3), an + nc ∈ o(bn ).


(b)  [2 marks] Prove that for all c > 0, nc ∈ ω((log n)2).


Solution

(1) Let c > 0 be arbitrary. We will show that nc ∈ ω((log n)2).

(2) By (1.2), log n ∈ o(nc/2).

(3) By (3.3) and (2), nc/2 ∈ ω(log n).

(4) Applying  (5.5) to  (3), we get  (nc/2)(nc/2)  ∈ ω((log n)(log n)), which simplifies to nc ∈ ω((log n)2).


(c)  [2 marks] Prove that for all c > 0, nc · 2n ∈ o(3n )


Solution

(1) Let c > 0 be arbitrary. We claim that nc · 2n ∈ o(3n ).

(2) By (1.4), nc ∈ o(()n ), since > 1.

(3) By (1.5), 2n ∈ o(()n ), since > 2.

(4) By applying (5.4) to (2) and (3), we see that nc · 2n ∈ o(()n · ()n ), which simplifies to nc · 2n ∈ o(3n ), as needed.


(d)  [4 marks] Prove that for all a > 0, n2 + an ∈ Θ(n2).

Solution

(1) Let a > 0 be arbitrary.  We will show that n2 + an ∈ Θ(n2).  By (3.1), it suffices to show that n2 + an ∈ O(n2) and n2 + an ∈ Ω(n2).

(2) By (5.1), n2 ∈ Θ(n2).

(3) By (3.1) and (2), n2 ∈ Ω(n2).

(4) By (4.2) and (3), n2 +an ∈ Ω(n2), as desired. It remains to show that n2 +an ∈ O(n2).

(5) Recall from (2) that n2 ∈ Θ(n2). By (3.1), n2 ∈ O(n2).

(6) By (5.1), an ∈ Θ(n).

(7) By (3.1) and (6), an ∈ O(n).

(8) By (1.3), n ∈ o(n2).

(9) By (3.4) and (8), n ∈ O(n2).

(10) By (2.1) applied to (7) and (9), an ∈ O(n2).

(11) By (4.1) applied to (5) and (10), n2 + an ∈ O(n2).

(12) Finally, by (3.1) applied to (4) and (11), 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).


Solution

(1) By (1.5), 2n ∈ o(3n ).

(2) By Question 4(a), 3n − 2n ∈ Θ(3n ).

(3) By (3.1) and (2), 3n − 2n ∈ O(3n ) and 3n − 2n ∈ Ω(3n ).

(4) By (3.2) applied to both statements in (3), 3n ∈ Ω(3n − 2n ) and 3n ∈ O(3n − 2n ).

(5) By (3.1) and (4), 3n ∈ Θ(3n − 2n )

(6) By Question 4(b) applied to (1) and (5), 2n ∈ o(3n − 2n ).

(7) By (3.3) and (6), 3n − 2n ∈ ω(2n ), as needed.


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)


(4.3) if f ∈ o(h) and g ∈ o(h), then f + g ∈ o(h)

(4.4) if f ∈ ω(h), then f + g ∈ ω(h)