Mathematical Foundation of Computer Science

DHARM

72 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Now analyze the equation (3.30) so we have following statements,

1. if a < b ⇒ x < 1 ; then summation converge, therefore T(n) = O(n).


2. if a = b ⇒ x = 1 ; then each term of the sum is unity, since there are O(log n) terms
   therefore, T(n) = O(n log n).


3. if a > b ⇒ x > 1; then sum terms grows exponentially and there summation is
   n(x1+logn – 1)/(x – 1) = O(a logbn) or equally O(n logba).
   The theorem states that dividing a problem into two subproblems of equal size results
   an O(n log n) time. If number of subproblems are 3, 4 or 8 then algorithm time would be n log^23 ,
   n log^24 = n^2 , n log^28 = n^3 respectively and so on. Dividing the problems into four subproblems of
   size n/4 (case 2 when a = b) results an O(n log n) and 9 and 16 subproblems give O(n log^48 ) and
   O(n log^416 ) = O(n^2 ).

3.6.2 Master Theorem...................................................................................................

Theorem 3.2. The solution of the recurrence equation
T(n) = a T(n/b) + f(n)
(where a ≥ 1, b >1 are constants) is given as,

T(n) =

θ

θθ

θ

() ()( )

( log ) ( ) ( )

(()) () ( )

log log

log log

log

nfnOn

nnfnn

fn fn n

bb

bb

b

aa

aa

a

if

if

if or

=

=

=

R

S

|

T

|

−∈

Ω +∈
f(n) = O(nlogba+δ) (3.31)
for some constant ∈ > 0 and some δ ≥ ∈.
By careful observation of the results obtain using master theorem we find that the
solution of the recurrence is based on the dominance of the function n logba and f(n). As in case
1, function n logba is dominant, so T(n) = θ(n logba). In case 3, function f(n) is dominant, so T(n)
= θ(f(n)). And as in case 2, two functions are same, so we multiply by a logarithmic factor, and
we obtain the solution T(n) = θ(n logba log n).

3.6.3 Substitution Method............................................................................................

Theorem 3.3. The solution of the recurrence

T(n) =

an

anb fn n

for

Tfor

=

+>

R

S

T

1
(/) ( ) 1
is given as T(n) = n logba [T(1) + g(n)] (3.32)

where g(n) =
j

i

hbj

=

∑

1

() and h(n) = f(n)/n logba

We obtain h(n) from the recurrence equation. Then find corresponding value of g(n)
from the table shown in Fig. 3.4. Entries of the table allows to obtain bounds of T(n) for many
recurrences we run-into using divide-and-conquer.

h(n) g(n)

O(nk) for k < 0 O(1)

θ( (log n)k) for k ≥ 0 θ( (log n)k+1)/(k + 1)

Ω(nk) for k > 0 θ(h(n))

Fig. 3.4