Mathematical Foundation of Computer Science

DHARM

RECURRENCE RELATIONS WITH CONSTANT COEFFICIENTS 71

Let T(n) be the time needed to sort an n-element array. When n ≤ 1, T(n) = a, for some

constant a. Assume n > 1, let s be the size of the left slice then size of the right slice will be

(n – s – 1) because pivot element is in middle. So the average time to sort the left slice is T(s)

and the right slice is T(n – s – 1) and the partitioning time f(n).

Since 0 ≤ s ≤ (n – 1), thus we obtain following recurrence

T(n) ≤

s

n

=

−

∑

0

1

(1/n) [T(s) + T(n–s–1)] + f(n)

That can be simplified to

T(n) =

s

n

=

−

∑

0

1

(2/n) T(s)+ f(n) ;

This recurrence is more complicated because value of T(n) depends on all earlier val-

ues. We can attempt some cleverness approach to solve this recurrence. We assume a case in

which quick sort works well such that on each time partition will split the set into two equal

halves (of size n/2). So we have more simplified recurrence equation,

T(n) = 2 T(n/2) + f(n) (3.28)

Therefore, T(n) is θ(n log n). [see example 3.9 (2)]

3.6 Method for Solving Recurrences.......................................................................................

Since recurrences of the form of (3.26) or (3.28) arises frequently in analyzing recursive divide-

&-conquer algorithms. We shall discuss the methods of finding of the solution of recurrences

in general. This section presents three methods for solving the recurrences which return the

solution in asymptomatic ‘θ’ or ‘O’ bounds. Theorem 3.1 illustrates Iteration method that

converts the recurrence into the summation of the terms then relies on techniques for bound-

ing summations to solve the recurrence. Master method (theorem 3.2) requires the memori-

zation of the cases that provides bounds for the recurrence of the form T(n) = a T(n/b) + f(n)

(where a ≥ 1, b ≥ 1) illustrated in theorem 3.2. At the end theorem 3.3 illustrates Substitution

method that guesses the bounds, corresponding to that it memorizes the appropriate bounds.

3.6.1 Iteration Method..................................................................................................

Theorem 3.1. Let a, b and c are nonnegative constants then solution to the recurrence

T(n) =

an

anb fn n

for

Tfor

=

+>

R

S

T

1

(/) ( ) 1

where n is a power of b is

T(n) =

Ofor

Ofor

O( for

()

( log )

log )

nab

nn ab

nabba

<

=

>

R

S

|

T|

(3.29)

Proof. Since n is a power of b, i.e. n = bk then

T(n) = n

k

b

k

n

x

=

∑

0

log

; (where x = a/b) (3.30)