Mathematical Foundation of Computer Science

DHARM

RECURRENCE RELATIONS WITH CONSTANT COEFFICIENTS 75

conclude that for n = 8 Stressman’s method is more efficient. In general, let T(n) denotes the
time required by the Stressman’s divide-and-conquer method, thus the recurrence is,

T(n) =

θ()

(/)

11

72182 1

for

Tfor

n

nn n

≤

+>

R

S

T

Solve this recurrence using theorem 3.3 (Method of substitution). Since, we have a = 7,

b = 2 and f(n) = 18 n^2. That gives h(n) = f(n)/n logba = 18 n^2 /n log^27 = 18 n2–log^27.

Since, 2 – log 2 7 < 0 therefore g(n) = O(1) (from the table shown in Fig. 3.4).

Hence, the solution T(n) = n log^27 [θ(1) + O(1)] = θ(n log^27 ) (assume θ(1) is constant).

= θ(n~−2.81)

Therefore, the time complexity of the matrix multiplication problem is θ(n2.81).

EXERCISES

3.1 Solve the recurrence an + 3 an–1 + 2 an–2 = f(n), where

fn()=RS n=

T

12

0

for

otherwise

and the base conditions a 0 = a 1 = 0.

3.2 Solve the following recurrence relations :

(i)an + an–1 + an–2 = 0, where a 0 = 0 and a 1 = 2.

(ii)an – an–1 – an–2 = 0, where a 0 = 0 and a 1 = 1.

(iii)an + 6an–1 + 9an–2 = 5n, where a 0 = 0 and a 1 = 2.

(iv)an + 3an–1 + 2an–2 = f(n), where f(n) = 6 for n = 2 and 0 otherwise with base conditions a 0 = 0

and a 1 = 0.

(v)an + 5an–1 + 6an–2 = f(n), where f(n) = 0 for n = 0, 1, 5 and 6 otherwise with a 0 = 0 and a 1 = 2.

(vi)an – 4an–1 + 4an–2 = 2n, where a 0 = 0 and a 1 = 0.

3.3 Solve the following difference equations :

(i)an^2 – 2an–1^2 = 1, where a 0 = 2.

(ii)nan + nan–1 – an–1 = 2n, where a 0 = 273.

(iii)an^2 – 2an–1 = 0, where a 0 = 4.

(iv)an – nan–1 = n!, for n ≥ 1 and a 0 = 2.

(v)an = aaannn−−− 123 +++......, where a 0 = 4.

3.4 Find the asymptotic order of the solutions for the following recurrence equations :

(i)T(n) = T(n/2) + c n log n (ii)T(n) = a T(n/2) + c nc

(iii)T(n) = 3T(n/2) + c n (iv)T(n) = 9T(n/2) + n^2 2 n

assume T(1) = 1, the recurrence is for n > 1 and c is some positive constant.

3.5 Let a problem of input size n is subdivided into n subproblems of size about n.

Show that the solution of the recurrence

T(n^2 /2r) = nT(n) + bn^2 (where r is an integer, r ≥ 1)

is O(n (log n)r log logn).

3.6 Equation (3.2) defined the Fibonacci sequence as fn = fn–1 + fn–2 for n >1, f 0 = 0 and f 1 = 1. Prove

the correct statement between the following :

(i) for n ≥ 1, fn ≤ 100 (3/2)n (ii) for n ≥ 1, fn ≥ .01 (3/2)n