Questions

1. This question refers to the following recurrence relation.

T(n) =

(a)  [3 marks] Use the substitution method to solve this recurrence relation.

Solution

By repeated substitution, we find

T(n)   =   3T(n − 1) + 3n − 1

=   3  3T(n − 2) + 3n −2   + 3n − 1

=   32T(n − 2) + 2 · 3n − 1

=   32   3T(n − 3) + 3n −3   + 2 · 3n − 1

=   33T(n − 3) + 3 · 3n − 1

=   ...

A reasonable guess is that, after j substitutions,

T(n) = 3jT(n − j) + j · 3n − 1 .

The recursion ends when we have T(n) written in terms of T(1).   This occurs when j = n − 1. According to our guess above, we get

T(n)   =   3n − 1T(1) + (n − 1) · 3n − 1

=   4 · 3n − 1 + (n − 1) · 3n − 1

=   n · 3n − 1 + 3 · 3n − 1

=   n · 3n − 1 + 3n .

Therefore our conjecture for the closed form solution to this recurrence relation is T(n) = n · 3n − 1 + 3n .

(b)  [3 marks] Prove that your solution from part (a) is correct using mathematical induction.

Solution

(1) Let P(n) be the predicate

T(n) = n · 3n − 1 + 3n .

We will prove P(n) for all n ≥ 1.

(2) Base case. When n = 1, we get T(1) = 4 from the recurrence relation, and n · 3n − 1 + 3n = 1 + 3 = 4.

Thus P(1) is true.

(3) Induction  step.   Let n  >  1 be arbitrary, and assume that P(k) is true for all 1 ≤ k < n. That is, assume that T(k) = k · 3k − 1 + 3k for any such k. We will prove that P(n) is true. That is, we will prove that T(n) = n · 3n − 1 + 3n .

(4) Using the recurrence relation, we get

T(n)

as needed.

=

=

=

=

3T(n − 1) + 3n − 1

3  (n − 1) · 3n −2 + 3n − 1   + 3n − 1     by induction hypothesis (n − 1) · 3n − 1 + 3n + 3n − 1

n · 3n − 1 + 3n ,

2. This question refers to the following recurrence relation.

0,

5

2 ,

T(n − 2) + 2n,

n = 1

n = 2

n > 2

(a)  [4 marks] Use the substitution method to solve this recurrence relation.  Consider the

case where n is odd only. You do not need to repeat your calculation for the case where n is even. Simplify your answer until no summation notation remains.

Solution

Assume that n is an odd number. By repeated substitution, we find

T(n)   =   T(n − 2) + 2n

=   T(n − 4) + 2(n − 2) + 2n

=   T(n − 6) + 2(n − 4) + 2(n − 2) + 2n

=   ...

A reasonable guess is that, after j substitutions,

T(n)   =   T(n − 2j) + 2n + 2(n − 2) + ... + 2(n − 2(j − 1))

j − 1

=   T(n − 2j) + 2X(n − 2k).

k=0

By assumption, n is odd. Therefore n − 2j is also odd, for all j. The recursion ends when n − 2j is one of the base cases. Specifically, it must be the odd base case, 1:

n − 1

2

Setting j = (n − 1)/2 in our proposed formula, we get

T(n)   =

=

=

=

(n −3)/2

T(1) + 2   X  (n − 2k)

k=0

(n −3)/2             (n −3)/2

0 + 2   X   n − 4   X   k

k=0                    k=0

n(n − 1) − 4 ·    · ·

1

(n − 1)(n + 3).

(b)  [3 marks] The closed form solution to this recurrence relation is

T(n) = ,    ∀n ≥ 1.

Prove that this solution is correct using mathematical induction.  Note that you do not need to separate the case where n is odd from the case where n is even.

Solution

(1) Let P(n) be the predicate

T(n) = .

We will prove P(n) for all n ≥ 1.

(2) Base  cases.   When n  =  1, we get T(1)  =  0 from the recurrence relation,  and (n − 1)(n + 3) = 0. Thus P(1) is true.

Similarly, when n = 2, we get T(2) = from the recurrence relation, and (n − 1)(n+3) = (2)(5) = . Thus P(2) is also true.

(3) Induction  step.   Let n  >  2 be arbitrary, and assume that P(k) is true for all 1 ≤ k < n. We will prove P(n).

(4) Using the recurrence relation, we have

T(n)   =   T(n − 2) + 2n

1

=      (n − 3)(n + 1) + 2n   by induction hypothesis

=      (n2 − 2n − 3 + 4n) = (n2 + 2n − 3) = (n − 1)(n + 3),

as needed.

3. This question refers to the following code.   Assume that the / symbol represents integer division: a/b = .

1       //pre: A.length  >=  1 ∧ 0  <= j,k < A.length

2      void myFnc(int[] A,  int  j,  int k)

3              if  (j  < k-2)

4                     nonsense(A,  j, k)

5                     myFnc(A,  (3*j+k)/4  +  1,  (j+k)/2)

6                     myFnc(A,  (j+k)/2  +  1,  (j+3*k)/4)

Let n = k − j + 1. Assume that nonsense(A,  j, k) performs some operation on the entries A[j], ..., A[k] inclusive, and that if this function acts on n entries, its cost is .

(a)  [3  marks] Let T(n) be the cost of myFnc() as a function of the input size n.   Find

the recurrence relation that defines T(n).  You will need to use the floor and/or ceiling functions. The only variable should be n: the indices j and k should not appear. (Caution: how many base cases do you need?)

Use the simplified conventions for counting steps that were described and used in the Week 6 notes.  For example, a fixed number of steps that does not depend on the size of n can be approximated by 1.  For any function f(n) such that f(n) ∈ ω(1), the sum f(n) + 1 can be approximated by f(n).

Solution

The given function only calls itself recursively if j < k − 2, or equivalently, if n = k −j+1 > 3. The values n ≤ 3 are base cases.

If n ≤ 3, then the if condition is checked and evaluates to false. This is a constant number of steps, which we approximate by 1.

Assume n > 3. Then myFnc calls itself recursively twice, in lines 5 and 6.

5

6

myFnc(A,  (3*j+k)/4  +  1,  (j+k)/2)

myFnc(A,  (j+k)/2  +  1,  (j+3*k)/4)

Recall that n = k − j + 1, which implies that k = n + j − 1.  In line 5, the number of

array entries being acted on is

− + 1 + 1

= −

= −

In line 6, the number of array entries being acted on is

− + 1 + 1   = −

= − = + j − − j               = − .

The local cost in the recursive case consists of a fixed number of steps plus the cost of line 4. This line acts on k − j + 1 = n entries, so its cost is . Thus the total local cost is a constant added to , which we approximate by .

The cost function T(n) for this function is defined by the recurrence relation

T(n) =

A = − ,    B = − .

For the remainder of this question, assume that n = 4r  for some r ≥ 0.

(b)  [2 marks] In the special case where n = 4r , show that your recurrence relation from part

(a) can be simplified to the following form.

T(n) =

Solution

Assume that n = 4r for some r ≥ 0. The recursive case occurs when n ≥ 4, which implies that r ≥ 1. In that case, observe that

= = 4r − 1

4       4              ,

= = 2 · 4r − 1

2       2                   ,

which are both integers. Using these expressions, the floor function terms that appear in A and B are

n − 1

Consequently,

=

B

= + − = − 1.

− 1 − − 1 = ,

− 1 − − 1 = .

Thus, in the special case where n = 4r, the recurrence relation from part (a) reduces to

T(n) =

(c)  [4 marks] Draw the recursion tree for your recurrence relation from part (b).  Include enough rows to establish a pattern for the entries.  Calculate the sum of each row, and use the result to conjecture a function g(n) so that T(n) ∈ Θ(g(n)).

Solution

Each node in the recursion tree has 2 child nodes. The inputs in each row are n, , , .... The entry in each node is obtained by applying the local cost function, f(n) = , to the input value. The result is:

...

The sum of each row is .  To estimate the total cost T(n), we need to estimate the number of rows.

The input in row j of the tree has the form .  Recursion is guaranteed to stop once = 1, which occurs when j = log4(n).  Thus there are approximately log4(n) rows in the tree, which suggests that T(n) is approximately log4(n).

Thus our conjecture for the asymptotic size of T(n) is

T(n) ∈ Θ(√nlog(n)).

(d)  [2 marks] Explain which case of the Master Theorem applies to the recurrence relation from part (b), and use that case to prove your conjecture from part (c).

Solution

Recall that the recurrence relation is

T(n) =

1,                     n ≤ 3

2T + ,   n > 3

This has the form given in the Master Theorem with a = 2, b = 4, and f(n) = = n1/2 .

Note that logb(a) = log4(2) = . Therefore f(n) ∈ Θ(nlogb(a)), which is the requirement

of Case 2 of the Master Theorem. The conclusion of Case 2 is

T(n) ∈ Θ(nlogb(a) log(n)),

which shows that

T(n) ∈ Θ(√nlog(n)).

This is the same asymptotic result that we guessed in part (c).