[3 marks]

Problem  1 Analyze the following piece of pseuodocode and give a tight (Θ) bound on the running time as a function of n. Briefly justify your answer (full proof not required).

x  =  1

while  x  <  n^3

x  *=  4

Solution:  The outer loop takes O(1) iterations, since 1,000,000 is a constant (albeit a large one). The inner loop takes Θ(log4 n3 ) iterations. We know that

log4 n3  =

3log n

=

log 4

∈ Θ(log n)

so the inner loop takes Θ(log n) iterations. Then since the body of the loop takes O(1) time, the overall running time is Θ(log n).

[2 + 3 = 5 marks]

Problem  2 Prove each of the following statements using the definition(s) of asymptotic notation (i.e. the definition of Big Oh, Theta notation).

(a) 3n4 + 2n3 + n2 + 5 ∈ O(n4 )

Solution: Let n0  = 1 and M = 11. Then, for any n > n0 ,

11 ≤ M

⇔ 11n4  ≤ Mn4

⇔ 3n4 + 2n4 + n4 + 5n4  ≤ Mn4

⇒ 3n4 + 2n3 + n2 + 5 ≤ Mn4  (since n > 1)

completing the proof.

(b) n2 +  ∈ Θ(n3 )

Solution: Let n0  = 1, M1  = , and M2  =  . Then, for all n > n0 ,

 ≥ M1

⇔  ≥ M1 n3

⇒  + n2  ≥ M1 n3 , since n > 0 ⇒ n2  > 0

⇒ n2 +  ≥ M1 n3 , since (cosn)3  ≤ 1

and

 ≤ M2

⇒  ≤ M2 n3

⇒ n3 +  ≤ M2 n3

⇒ n2 +  ≤ M2 n3 , since n > 1 ⇒ n3  > n2

⇒ n2 +  ≤ M2 n3 , since (cosn)3  ≥ −1

completing the proof.

[2 + 3 = 5 marks]

Problem  3 For each of the following determine if f(n)  ∈  o(g(n)),  f(n)  ∈ ω(g(n)), or f(n) ∈ Θ(n).  Justify your answer.  In your justification, you may use any facts or techniques discussed in the lectures.

(a) f(n) = n1+ϵ  (ϵ > 0) and g(n) = nlog n

Solution:

n1+ϵ                         nϵ   

n →∞ nlogn     n →∞ log n

ϵnϵ −1

= nl  n −1   , by L’Hopital’s rule

= ϵ  lim  nϵ  = ∞

→∞

and so we conclude that n1+ϵ  ∈ ω(nlog n).

(b) f(n) = √n and g(n) = (log n)4

Solution: We will use the same technique as for part (a), except with several applications of L’Hopital’s rule.

n1/2           1           n1/2  

n →∞ log4 n      8 n →∞ log3 n

1            n1/2  

48 n →∞ log2 n

1            n1/2

192 n →∞ log n

=   1   lim  n1/2  = ∞

[5 + 5 = 10 marks]

Problem 4 Prove or disprove each of the following statements. To prove a state- ment, you should provide a formal proof using the definition(s) of asymptotic notation.  To disprove a statement, you may either provide a counter-example and explain it or provide a formal proof.

(a) f(n)  o(g(n)) and f(n)  ω(g(n)) ⇒ f(n) ∈ Θ(g(n)).

Solution: The statement is not true. To see this, consider the following func- tions f and g:

f(n) = (n(n)2 g(n) = (n(n)2

, if ⌊n⌋ is even

, otherwise

, if ⌊n⌋ is even

, otherwise

First,  let’s show that  f(n)    o(g(n)).   Let M  =  1,n0   >  0,  and choose n to be the smallest odd number larger than 1 and n0 .  Then we know that f(n) = n2 ,g(n) = n, so, since n > 1, f(n) > Mg(n).

Next, let’s show that f(n)  ω(g(n)). Let M = 1,n0  > 0, and choose n to be the smallest even number larger than 1 and n0 . Then f(n) = n and g(n) = n2 . Thus, since n > 1,f(n) < Mg(n).

Finally, let’s show that f(n)  O(g(n)) (which implies that f(n)  Θ(g(n))). Let M > 0 and n0  > 0.  Then choose n to be the smallest odd number larger than n0  and M . Then we know that

n > M

⇒ n2  > Mn

⇒ f(n) > Mg(n)

completing the proof.

(b) f(n) ∈ Θ(g(n)) and g(n) ∈ o(h(n)) ⇒ h(n) ∈ ω(f(n)).

Solution:  The statement is true.   Let M1 ,M2 ,n  >  0 be so that,  for all n > n ,

M1g(n) ≤ f(n) ≤ M2g(n)

Let M > 0. We want to show that, for some n0  > 0 and all n ≥ n0 , h(n) ≥ Mf(n)

Let M′ =  and let n be so that for all n > n ,

g(n) ≤ M′ h(n)

which we can do since g(n) ∈ o(h(n)).

Let n0  = max{n,n}. Then, for all n > n0 ,

h(n) ≥ g(n) ≥ f(n) = Mf(n)

completing the proof.

[3 + 3 + 3 + 3 + 3 = 15 marks]

Problem 5 For each of the following recurrences, determine if we can solve it using the Master Theorem.  If we can, then solve it with the Master Theorem. If not, explain why not.

(a) T(n) =

Solution:  a = 125,b = 5, so we consider n3 , and f(n) =  .  We know that  ∈ o(n3 ), however we cannot say that  ∈ O(n3−ϵ ) for any ϵ > 0. To see this, consider the following limit:

lim     =  lim        n3         

n →∞ n −ϵ log n

nϵ   

n →∞ log n

and we have seen that this limit goes to ∞ in the solution to problem 3(a). This shows that  ∈ ω(n3−ϵ ) for all ϵ, so f(n)  O(n3−ϵ ). Thus, case 1 of the master theorem does not apply. For case 2, we have that f(n) ∈ Θ(n3 (log n)k )

for k = − 1.  However, we require that k ≥ 0, so case 2 of the master theorem

(b) T(n) = 

Solution:  a  = 650,b  =  5, so we consider n4   (though the exponent will be slightly larger than 4).  Then for ϵ = 0.5, we have that n3 /log n ∈ O(n4−ϵ ), so we can apply the master theorem to get that T(n) ∈ Θ(n4 ).

(c) T(n) = (3(1)T(n/2) + n1 .57

, if n ≤ 1

, otherwise

Solution:  a  = 3,b  = 2, so we consider n1 .58   (though the exponent will be slightly larger than this). Then we have that for ϵ = 0.001, n1 .57  ∈ O(n1 .58−ϵ ), so we can apply the master theorem to get that T(n) ∈ Θ(nlog 3 )

(d) T(n) = (3(1)T(n/2) + n2      ,

Solution:  a  = 3,b  = 2, so we

if n ≤ 1

otherwise

consider n1 .59   (though the exponent will be

slightly smaller than this). Then we have that, for ϵ = 0.1, n2  ∈ Ω(n1 .59+ϵ). We also have that, for c =  ,

3   2  = 3  ≤ cn2

so the regularity condition holds. Thus we can apply the master theorem to get that T(n) ∈ Θ(n2 ).

(e) T(n) = (4(1)T(n/2) + n2 (log n)5

, if n ≤ 1

, otherwise