Recurrence Relation

What is recurrence relation?

To be discussed
• Definition
• Formation of recurrence relation
• Methods to solve recurrence relation
• Master theorem for dividing function

~ Rezaur Rahman
S.No.: 47
Class: IT-2, 5th Sem
 Recurrences and Examples
• An equation that defines a sequence based on a rule that
gives the next term as a function of the previous term(s).
T(n) = T(n-1) + n
• Recurrences arise when an algorithm contains recursive
calls to itself
• Example: Fibonacci series where succeeding terms are

dependent on last two preceding terms.

f(n)=f(n-1)+f(n-2)

with the initial values f(0)=0 and f(1)=1

2
 Example Recurrences
• T(n) = T(n-1) + n Θ(n2)
– Recursive algorithm that loops through the input to
eliminate one item
• T(n) = T(n/2) + c Θ(lgn)
– Recursive algorithm that halves the input in one step
• T(n) = T(n/2) + n Θ(n)
– Recursive algorithm that halves the input but must
examine every item in the input
• T(n) = 2T(n/2) + 1 Θ(n)
– Recursive algorithm that splits the input into 2 halves
and does a constant amount of other work

3
 Recurrent Algorithms
BINARY-SEARCH
• for an ordered array A, finds if x is in the array A[lo…hi]

Alg.: BINARY-SEARCH (A, lo, hi, x)

1 2 3 4 5 6 7 8

if (lo > hi) 2 3 5 7 9 10 11 12

return FALSE
mid  (lo+hi)/2 mid
if x = A[mid] lo hi

return TRUE
if ( x < A[mid] )
BINARY-SEARCH (A, lo, mid-1, x)
if ( x > A[mid] )
BINARY-SEARCH (A, mid+1, hi, x)

4
 Analysis of BINARY-SEARCH
Alg.: BINARY-SEARCH (A, lo, hi, x)
if (lo > hi) constant time: c1
return FALSE
mid  (lo+hi)/2 constant time: c2
if x = A[mid]
constant time: c3
return TRUE
if ( x < A[mid] )
BINARY-SEARCH (A, lo, mid-1, x)same problem of size n/2
if ( x > A[mid] )
BINARY-SEARCH (A, mid+1, hi, x)same problem of size n/2

• T(n) = c + T(n/2)
– T(n) – running time for an array of size n
5
 Methods for Solving Recurrences

• Substitution method(iteration)

• Recursion tree method

• Master method

6
 The Substitution Method
• Convert the recurrence into a summation and try
to bound it using known series
– Use back-substitution to express the recurrence in
terms of n and the initial (boundary) condition.
– Iterate the recurrence until the initial condition is
reached.

7
 Substitution Method - Examples
T(n) = 1 + T(n/2)
T(n) = 1 + T(n/2) T(n/2) = 1 + T(n/4)
= 1 + 1 + T(n/4) T(n/4) = 1 + T(n/8)
= 1 + 1 + 1 + T(n/8)
After substituting for k times, we get
T(n) = 1 + 1 + … + 1 + T(n/ 2k)
k times
= k + T(n/ 2k)
Now T(n/ 2k) = T(1)

8
 Substitution Method - Examples
=> n/ 2k = 1
=> 2k = n
=> k = log(n)
Time complexity= Θ(log n)

9
 Substitution Method – Examples
T(n) = n + 2T(n/2)
T(n) = n + 2T(n/2) T(n/2) = n/2 + 2T(n/4)
= n + 2(n/2 + 2T(n/4))
= n + n + 4T(n/4)
= n + n + 4(n/4 + 2T(n/8))
= n + n + n + 8T(n/8)
…
After k times, we get
T(n) = kn + 2kT(n/2k) …(i)

10
 Substitution Method - Examples
Assume T(n/2k) = T(1)
n/2k = 1
2k = n …(ii)
k= log n …(iii)
Put (ii) & (iii) in (i), we get
T(n) = n T(1) + k n
T(n) = n x 1 + n log (n)
T(n) = n + n log (n)

So,Time complexity= Θ(n log n)

11
The recursion-tree method

Convert the recurrence into a tree:

– Each node represents the cost incurred at various
levels of recursion
– Sum up the costs of all levels

Used to “guess” a solution for the recurrence

12
 Example 1
W(n) = 2W(n/2) + n2

• Subproblem size at level i is: n/2i

• Subproblem size hits 1 when 1 = n/2i  i = lgn
• Cost of the problem at level i = (n/2i)2 No. of nodes at level i = 2i
• Total cost: lg n 1 2 lg n 1 i  i
n 1 1 1
W ( n)  2
i 0
i
 2lg n W (1)  n 2     n  n 2     O(n) n 2
i 0  2  i 0  2  1 1
 O ( n)  2n 2
2
 W(n) = O(n2)
13
 Example 2
E.g.: T(n) = 3T(n/4) + cn2

• Subproblem size at level i is: n/4i

• Subproblem size hits 1 when 1 = n/4i  i = log4n
• Cost of a node at level i = c(n/4i)2
• Number of nodes at level i = 3i  last level has 3log4n = nlog43 nodes
• Total cost:
log4 n 1 i i

     

3 2 3 1
T ( n)     cn   n
 16 
log4 3
    cn 2   n log4 3 
i  0  16 
3
cn 2   n log4 3  O(n 2 )
i 0
1
16 14
 T(n) = O(n2)
 Example 2 – Solving by substitution
method
T(n) = 3T(n/4) + cn2 …(i)

first find T(n/4) from above relation, we get

=> T(n/4) = 3T(n/42) + c(n/4)2
=> 3T(n/4) = 32T(n/42) + 3c(n/4)2 …(ii)
put (ii) in (i), we get
=> T(n) = 32T(n/42) + 3c(n/4)2 + cn2 …(iii)

Now, find T(n/42) from eq.(i), we get

=> T(n/42) = 3T(n/43) + c(n/42)2
=> 32T(n/42) = 33T(n/43) + 32c(n/42)2 …(iv)
put (iv) in (iii), we get
T(n) = 33T(n/43) + 32c(n/42)2 + cn2

After k times, we get (where k is large)

T(n) = 3kT(n/4k) + cn2 + 32c(n/42)2 + 33c(n/43)2 + ……… + 3k-1c(n/4k-1)2

15
 Solving by substitution method
T(n) = 3kT(n/4k) + cn2 + 32c(n/42)2 + 33c(n/43)2 + ……… + 3k-1c(n/4k-1)2
= cn 2(1 + 3/42 + (3/42)2 + (3/42)3 + ……)

Clearly, we can see in above equation it is forming GP series.

Also, the common ratio is 3/42 = 3/16 which is less than 1.
Formula: Sum of infinite GP series =
where a= first term
and r = common ratio

T(n) = cn2[
T(n) = d n2 where d is some constant
Θ(n2)

16
 Example 3 (simpler proof)
W(n) = W(n/3) + W(2n/3) + n

• The longest path from the root to

a leaf is:
n  (2/3)n  (2/3)2 n  …
1
• Subproblem size hits 1 when
1 = (2/3)in  i=log3/2n

• Cost of the problem at level i = n

• Total W
cost: lg n
(n)  n  n  ...  n(log 3/ 2 n)  n  O(n lg n)
3
lg
2
17
 Example 3 - Substitution
W(n) = W(n/3) + W(2n/3) + n …(i)
=> W(n/3) = W(n/32) + W(2n/32) + n/3 …(ii)
=> W(2n/3) = W(2n/32) + W(n(2/3)2) + 2n/3 …(iii)
Put (ii) & (iii) in (i), we get

=> W(n) = W(n/32) + 2W(2n/32) + W(n(2/3)2) + n + n

After k times, we get
=> W(n) = W(n/3k) + k W(2n/3k) + W(n(2/3)k) + n + n + ……+ n
{k times)
=> W(n) = W(n(2/3)k) + k n …(iv)
Now we will find the value of k

=> W(n(2/3)k) =W(1)

=> n(2/3)k = 1
=> n = (3/2)k
18
 Solving by substitution method
=> log n = k log(3/2)

=> k =
Now from equation (iv), we have
W(n) = W(n(2/3)k) + k n …(iv)

Time complexity = O(k n)

But k log n
So, time complexity = O(n log n)

19
 Master’s method
• For solving recurrences of the form:
n
T ( n)  aT    f ( n)
b
where, a ≥ 1, b > 1, and f(n) = Θ(nk logp n)
Case1: if logab > k , then Θ(nlogab)

Case2: if logab = k
if p > -1, Θ(nk logp+1 n)
if p = -1, Θ(nk log log n)
if p > -1, Θ(nk)

Case3: if logab < k

if p 0, Θ (nk logp n)
if p 0, Θ (nk) 20
 Examples
T(n) = 2T(n/2) + n
n
Sol: Compare it with
T ( n )  aT    f ( n)
b
Where f(n) = Θ(nk logp n)
a = 2, b = 2, k = 1, p = 0, log 22 = 1 = k
logab = k ……… ( case 2)

Case2: if logab = k
if p > -1, Θ(nk logp+1 n)
if p = -1, Θ(n log log n)
if p > -1, Θ(nk)

Clearly here p = 0. So p > -1

Case2: if logab = k
if p > -1, Θ(nk logp+1 n)
21
Time Complexity = Θ(n log n)
 Examples
T(n) = 2T(n/2) + n2
n
T (
Sol: Compare it with n )  aT    f ( n)
b
Where f(n) = Θ(nk logp n)

a = 2, b = 2, k=2, p = 0
=> log22 = 1 k (Case 3)

Case3: if logab < k)

if p 0, Θ (nk logp n)
if p 0, Θ (nk)

Θ(n2)

22
 Examples

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

Sol: Compare it with

n
T ( n)  aT    f ( n)
b
Where f(n) = Θ(nk logp n)
=> a = 2, b = 2, k = , p = 0
=> log22 = 1 k ( Case 1)

Case1: if logab > k , then Θ(nlogab)

Time Complexity= Θ(n)

23
 Examples

T(n) = 3T(n/4) + n log n

n
T ( n)  aT    f ( n)
Sol: Compare it with
b
Where f(n) = Θ(nk logp n)
=> a = 3, b = 4, k = 1, p = 1,

=> log43 = 0.793 k ( Case 3 Problem)

Case3: if logab < k

if p 0, Θ (nk logp n)
if p 0, Θ (nk)

In above example, p = 1 0

Time Complexity= Θ (n log n) 24

 Examples
T(n) = 2T(n/2) +
Sol: Compare it with
n
T ( n)  aT    f ( n)
where f(n) = Θ(nk logp n)  b 

=> a = 2, b = 2, k = 1, p = -1

=> log22 = 1 = k case 2 problem

Case2: if logab = k
if p > -1, Θ(nk logp+1 n)
if p = -1, Θ(nk log log n)
if p > -1, Θ(nk)
We have p = -1

Case2: if logab = k
if p = -1, Θ(nk log log n)

Time complexity = Θ(n log log n)

25