Recurrence relation solutions

Computer Algorithms
Design and Analysis
UNIT-I
Recurrence Relations
Dr. N. Subhash Chandra,
Professor, CVRCE
Source: Web resources ,Computer Algorithms by Horowitz, Sahani & Rajasekaran.
Algorithm by Coreman

Need of Recursive Relations
25/07/2020 2

Recurrence Relations (1/2)
• A recurrence relation is an equation which is
defined in terms of itself with smaller value.
• Why are recurrences good things?
• Many natural functions are easily expressed as
recurrences:
• an = a n-1 + 1, a1 = 1 --> an = n (polynomial)
• an = 2a n-1 ,a1 = 1 --> an = 2n (exponential)
• an = na n-1 ,a1 = 1 --> an = n! (weird function)
• It is often easy to find a recurrence as the solution
of a counting problem
25/07/2020 3

Recurrence Relations (2/2)
• In both, we have general and boundary conditions,
with the general condition breaking the problem
into smaller and smaller pieces.
• The initial or boundary condition terminate the
recursion.
25/07/2020 4

Recurrence Equations
• A recurrence equation defines a function, say T(n). The function is
defined recursively, that is, the function T(.) appear in its definition.
(recall recursive function call). The recurrence equation should have a
base case.
For example:
T(n) = T(n-1)+T(n-2), if n>1
1, if n=1 or n=0.
base case
for convenient, we sometime write the recurrence equation as:
T(n) = T(n-1)+T(n-2)
T(0) = T(1) = 1.
25/07/2020 5

Recurrence Examples







0
0
)1(
0
)(
n
n
nsc
ns






0)1(
00
)(
nnsn
n
ns














1
2
2
1
)(
nc
n
T
nc
nT















1
1
)(
ncn
b
n
aT
nc
nT
25/07/2020 6

Methods for Solving Recurrences
• Iteration method ( Backward Substitution Method
• Substitution method
• Recursion tree method
• Master method
725/07/2020

Simplications:
• There are two simplications we apply that won't
affect asymptotic analysis
• Ignore floors and ceilings (justification in text)
• Assume base cases are constant, i.e., T(n) = Q(1) for n
small enough
25/07/2020 8

Iteration Method (Backward
Substitution )
• Expand the recurrence
• Work some algebra to express as a
summation
• Evaluate the summation
25/07/2020 9

Iteration Method
T(n) = c + T(n/2)
T(n) = c + T(n/2)
= c + c + T(n/4)
= c + c + c + T(n/8)
Assume n = 2k k=log
2
n
T(n) = c + c + … + c + T(1)
= clog2n + T(1)
= Θ(lgn)
10
k times
T(n/2) = c + T(n/4)
T(n/4) = c + T(n/8)
25/07/2020







0)1(
00
)(
nnsc
n
ns
• s(n) =
c + s(n-1)
c + c + s(n-2)
2c + s(n-2)
2c + c + s(n-3)
3c + s(n-3)
…
kc + s(n-k) = ck + s(n-k)
• What if k = n?
• s(n) = cn + s(0) = cn
25/07/2020 11

Iteration Method
Example: T(n) = 4T(n/2) + n
T(n) = 4T(n/2) + n /**T(n/2)=4T(n/4)+n/2
= 4(4T(n/4)+n/2) + n /**simplify**/
= 16T(n/4) + 2n + n /**T(n/4)=4T(n/8)+n/4
= 16(4T(n/8+n/4)) + 2n + n /**simplify**/
= 64(T(n/8) +4n+2n+n
= 4log n T(1)+ … + 4n + 2n + n /** #levels = log n **/
= c4log n + /** convert to summation**/
/** alog b = blog a **/
k1-nlog
0k
2n 
)
12
12
(
log
4log



n
ncn
25/07/2020 12

Solving Recurrences: Iteration
(convert to summation) (cont.)
= cn2+n(nlog 2 -1) /** 2log n = nlog 2 **/
= cn2 +n(n - 1)
= cn2 +n2 - n
= Q(n2)
25/07/2020 13

T(n – 1) = T(n – 2) + n – 1
Substituting (2) in (1) T(n) = T(n
– 2) + n – 1+ n
T(n – 2) = T(n – 3) + n – 2
Substituting (4) in (3)
T(n) = T(n – 3) + n – 2 + n – 1 + n
General equation
…..(2)
…..(3)
…..(4)
…..(5)
T(n) = T(n – k) + (n – (k – 1)) + n – (k – 2) + n – (k – 3) + n – 1 + n
…..(6)
T(1) =1
n – k =1
k = n – 1
T(n) = T(1) + 2 + 3 + ….. n – 1 + n
=1 + 2 + 3 + ….. + n
= n(n + 1)/2 T(n) = O( n2
)
…..(7)
25/07/2020 14

T(n) = 1
Solution:
T(n) = T(n – 1) + b
T(n – 1) = T(n – 2) + b
T(n) = T(n – 2) + b + b
T(n) = T(n – 2) + 2b
T(n – 2) = T(n – 3) + b
T(n) = T(n – 3) + 3b
General equation T(n)
= T(n – k) + k.b T(1)
= 1
n – k = 1 k = n – 1
T(n) = T(1) + (n – 1) b
= 1 + bn – b T(n) =
O(n)
n = 1
…..(1)
…..(2)
…..(3)
…..(4)
2. T(n) = T(n – 1) + b n > 1
25/07/2020 15

3. T(n) = 2 T(n – 1) + b
T(n) = 1
Solution:
T(1) = 1
T(2) = 2.T(1) + b
= 2 + b
= 21
+ b
T(3) = 2T(2) + b
= 2(2 + b) + b
= 4 + 2b + b
= 4 + 3b
= 22
+ (22
– 1)b T(4) =
2.T(3) + b
= 2(4 + 3b) + b
= 8 + 7b
= 23
+ (23
–1)b
General equation
T(k) = 2k–1
+ (2k–1
– 1)b
.
n > 1
n = 1
25/07/2020 16

.
.
T(n) = 2n–1
+ (2n–1
– 1)b
T(n) = 2n–1
(b + 1) – b
= 2n
(b + 1)/2 – b Let c
= (b + 1)/2 T(n) = c 2n
– b
= O(2n
)
4. T(n) = T(n/2) + b
T(1) = 1
Solution:
T(n) = T(n/2) + b
T(n/2) = T(n/4) + b
T(n) = T(n/4) + b + b
= T(n/4) + 2b
T(n/4) = T(n/8) + b
n > 1
n = 1
…..(1)
…..(2)
…..(3)
…..(4)
25/07/2020 17

T(n) = T(n/8) + 3b
= T(n/23
) + 3b
General equation
T(n) = T(n/2k
) + kb
T(1) = 1
n/2k
= 1
2k
= n
K = log n
T(n) = T(1) + b.log n
= 1 + b log n T(n) =
O(log n)
…..(5)
…..(6)
25/07/2020 18

The substitution method
1. Guess a solution
2. Use induction to prove that the
solution works
1925/07/2020

Substitution method
• Guess a solution
• T(n) = O(g(n))
• Induction goal: apply the definition of the asymptotic notation
• T(n) ≤ d g(n), for some d > 0 and n ≥ n0
• Induction hypothesis: T(k) ≤ d g(k) for all k < n
• Prove the induction goal
• Use the induction hypothesis to find some values of the
constants d and n0 for which the induction goal holds
2025/07/2020

Example: Binary Search
T(n) = c + T(n/2)
• Guess: T(n) = O(lgn)
• Induction goal: T(n) ≤ d lgn, for some d and n ≥ n0
• Induction hypothesis: T(n/2) ≤ d lg(n/2)
• Proof of induction goal:
T(n) = T(n/2) + c ≤ d lg(n/2) + c
= d lgn – d + c ≤ d lgn
if: – d + c ≤ 0, d ≥ c
2125/07/2020

Example 2
T(n) = T(n-1) + n
• Guess: T(n) = O(n2)
• Induction goal: T(n) ≤ c n2, for some c and n ≥ n0
• Induction hypothesis: T(k-1) ≤ c(k-1)2 for all k < n
T(n) = T(n-1) + n ≤ c (n-1)2 + n
= cn2 – (2cn – c - n) ≤ cn2
if: 2cn – c – n ≥ 0  c ≥ n/(2n-1)  c ≥ 1/(2 – 1/n)
• For n ≥ 1  2 – 1/n ≥ 1  any c ≥ 1 will work
2225/07/2020

Example 3
T(n) = 2T(n/2) + n
• Guess: T(n) = O(nlgn)
• Induction goal: T(n) ≤ cn lgn, for some c and n ≥ n0
• Induction hypothesis: T(n/2) ≤ cn/2 lg(n/2)
T(n) = 2T(n/2) + n ≤ 2c (n/2)lg(n/2) + n
= cn lgn – cn + n ≤ cn lgn
if: - cn + n ≤ 0  c ≥ 1
2325/07/2020

Changing variables
n
• Rename: m = lgn  n = 2m
T (2m) = 2T(2m/2) + m
• Rename: S(m) = T(2m)
S(m) = 2S(m/2) + m  S(m) = O(mlgm)
(demonstrated before)
T(n) = T(2m) = S(m) = O(mlgm)=O(lgnlglgn)
Idea: transform the recurrence to one that you have
seen before
24
T(n) = 2T( ) + lgn
25/07/2020

Recursion Tree
• Evaluate: T(n) = T(n/2) + T(n/2) + n
• Work copy: T(k) = T(k/2) + T(k/2) + k
• For k=n/2, T(n/2) = T(n/4) + T(n/4) + (n/2)
• [size|cost]
25/07/2020 25

Recursion-tree method
• A recursion tree models the costs (time) of
a recursive execution of an algorithm.
• The recursion tree method is good for
generating guesses for the substitution
method.
• The recursion-tree method can be
unreliable.
• The recursion-tree method promotes
intuition, however.
25/07/2020 26

Recursion Tree
• To evaluate the total cost of the recursion tree
Sum all the non-recursive costs of all nodes
= Sum (rowSum(cost of all nodes at the same depth))
• Determine the maximum depth of the recursion tree:
For our example, at tree depth d
the size parameter is n/(2d)
the size parameter converging to base case, i.e. case 1
such that, n/(2d) = 1,
d = lg(n)
The row Sum for each row is n
• Therefore, the total cost, T(n) = n lg(n)
25/07/2020 27

Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
25/07/2020 28

T(n)
Solve T(n) = T(n/4) + T(n/2) + n2:
25/07/2020 29

T(n/4) T(n/2)
n2
Solve T(n) = T(n/4) + T(n/2) + n2:
25/07/2020 30

Solve T(n) = T(n/4) + T(n/2) + n2:
n2
(n/4)2 (n/2)2
T(n/16) T(n/8) T(n/8) T(n/4)
25/07/2020 31

(n/16)2 (n/8)2 (n/8)2 (n/4)2
(n/4)2 (n/2)2
Q(1)
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
25/07/2020 32

Solve T(n) = T(n/4) + T(n/2) + n2:
(n/16)2 (n/8)2 (n/8)2 (n/4)2
(n/4)2 (n/2)2
Q(1)
2nn2
25/07/2020 33

Solve T(n) = T(n/4) + T(n/2) + n2:
(n/16)2 (n/8)2 (n/8)2 (n/4)2
(n/4)2 (n/2)2
Q(1)
2
16
5 n
2nn2
25/07/2020 34

Solve T(n) = T(n/4) + T(n/2) + n2:
(n/16)2 (n/8)2 (n/8)2 (n/4)2
(n/4)2
Q(1)
2
16
5 n
2n
2
256
25 n
n2
(n/2)2
…
25/07/2020 35

Solve T(n) = T(n/4) + T(n/2) + n2:
(n/16)2 (n/8)2 (n/8)2 (n/4)2
(n/4)2
Q(1)
2
16
5 n
2n
2
256
25 n
    1
3
16
52
16
5
16
52
n
…
Total =
= Q(n2)
n2
(n/2)2
geometric series
25/07/2020 36

• Example
T (n) = 2T (n/2) + n2
25/07/2020 37

Example : T (n) = 4T (n/2)+n
25/07/2020 39

Let k th steps, it moves up to n/3k
It moves until 1
The total sum up to kth step =kn
If n/3k = 1
n = 3k
k= logn
Total time taken =nlogn
25/07/2020 42

The Master Method
• Based on the Master theorem.
• “Cookbook” approach for solving recurrences of the
form
T(n) = aT(n/b) + f(n)
• a  1, b > 1 are constants.
• f(n) is asymptotically positive.
• n/b may not be an integer, but we ignore floors and ceilings.
• Requires memorization of three cases.
25/07/2020 43

The Master Theorem
Theorem 4.1
Let a  1 and b > 1 be constants, let f(n) be a function, and
Let T(n) be defined on nonnegative integers by the recurrence
T(n) = aT(n/b) + f(n), where we can replace n/b by n/b or n/b.
T(n) can be bounded asymptotically in three cases:
1. If f(n) = O(nlogba–) for some constant  > 0, then T(n) = Q(nlogba).
2. If f(n) = Q(nlogba), then T(n) = Q(nlogbalg n).
3. If f(n) = (nlogba+) for some constant  > 0,
and if, for some constant c < 1 and all sufficiently large n,
we have a·f(n/b)  c f(n), then T(n) = Q(f(n)).
25/07/2020 44

Master Method – Examples
• T(n) = 16T(n/4)+n
• a = 16, b = 4, nlogba = nlog416 = n2.
• f(n) = n = O(nlogba-) = O(n2- ), where  = 1  Case 1.
• Hence, T(n) = Q(nlogba ) = Q(n2).
• T(n) = T(3n/7) + 1
• a = 1, b=7/3, and nlogba = nlog 7/3 1 = n0 = 1
• f(n) = 1 = Q(nlogba)  Case 2.
• Therefore, T(n) = Q(nlogba lg n) = Q(lg n)
25/07/2020 45

• T(n) = 3T(n/4) + n lg n
• a = 3, b=4, thus nlogba = nlog43 = O(n0.793)
• f(n) = n lg n = (nlog43 +  ) where   0.2  Case 3.
• Therefore, T(n) = Q(f(n)) = Q(n lg n).
• T(n) = 2T(n/2) + n lg n
• a = 2, b=2, f(n) = n lg n, and nlogba = nlog22 = n
• f(n) is asymptotically larger than nlogba, but not
polynomially larger. The ratio lg n is asymptotically less than
n for any positive . Thus, the Master Theorem doesn’t
apply here.
25/07/2020 46

 T(n) = 9T(n/3) + n
 a=9, b=3, f(n) = n
 nlogba = nlog39 = Q(n2)
 Since f(n) = n, f(n)< nlogba
 Case 1 applies:
T(n)  Qnlogb a
when f (n)  Onlogb a

 Thus the solution is T(n) = Q(n2)
25/07/2020

Problems on The Master Method
 T(n) = 4T(n/2) + n2
 a = 4, b = 2, f(n)=n2
 nlogba = n2
 Since, f(n)=n2
 Thus, f(n)= nlogba
 Case 2 applies:
f (n) = Q(n2logn)
 Thus the solution is T(n) = Q(n2logn).
25/07/2020





 Ex. T(n) = 4T(n/2) + n3
a = 4, b = 2, f(n)=n3 nlogba
= n2; f (n) = n3.
Since, f(n)=n3 Thus, f(n)> nlogba
 Case 3 applies:
f (n) =(n3)
 and 4(n/2)3  cn3 (regulatory condition) for c =1/2.
T(n) = Q(n3).
25/07/2020

1. T(n) = 4T(n/2) + n
T(n) = 1
n > 1
n = 1
From the above recurrence relation we obtain
a = 4, b = 2, c = 1, d = 1, f(n) = n
logba = log24 = log222
= 2 log22 = 2
nlog a
= n2
b
25/07/2020 50

f(n) = O(n2
)
n = O(n2
) It will fall in Case 1. So that
T(n) = (n2
)
2. T(n) = 4T(n/2) + n2
n > 1 T(n) = 1 n = 1
From the above recurrence relation we obtain a = 4, b = 2, c = 1, d = 1, f(n) =
n2
nlog a
= n2
b
f(n) = n2
) n2
= (n2
)
It will fall in case 2.
T(n) = (n2
log n)
3. T(n) = 4T(n/2) + n3
T(n) =1
n > 1
n = 1
From the above recurrence relation we obtain
a = 4, b = 2, c = 1, d = 1, f(n) = n3
nlog a
= n3
b
f(n) = Ω(nlog
b
a + €)
25/07/2020 51

25/07/2020 55

Some Common Recurrence Relation
Recurrence Relation Complexity Problem
T(n) = T(n/2) + c O(logn) Binary Search
T(n) = 2T(n-1) + c O(2n) Tower of Hanoi
T(n) = T(n-1) + c O(n) Linear Search
T(n) = 2T(n/2) + n O(nlogn) Merge Sort
T(n) = T(n-1) + n O(n2) Selection Sort,
Insertion Sort
T(n) = T(n-1)+T(n-2) + c O(2n) Fibonacci Series
25/07/2020

Recurrence relation solutions

Recommended

More Related Content

What's hot (20)

Similar to Recurrence relation solutions (20)

More from subhashchandra197 (17)

Recently uploaded (20)

Recurrence relation solutions