Recurrence relation solutions

....

1. 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

2. Need of Recursive Relations
25/07/2020 2

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

4. 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

5. 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

6. 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

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

8. 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

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

10. 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 = 2
k k=log
2
n
T(n) = c + c + … + c + T(1)
= clog
2n + T(1)
= Θ(lgn)
10
k times
T(n/2) = c + T(n/4)
T(n/4) = c + T(n/8)
25/07/2020

11. 





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

12. 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
= 4
log n
T(1)+ … + 4n + 2n + n /** #levels = log n **/
= c4
log n
+ /** convert to summation**/
/** a
log b
= b
log a
**/k
1-n log
0 k
2n
 )
12
12
(
log
4log



n
ncn
25/07/2020 12

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

14. 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
Substituting (7) in (6)
T(n) = T(1) + 2 + 3 + ….. n –1 + n
=1 + 2 + 3 + ….. + n
= n(n + 1)/2 T(n) = O( n
2
)
…..(7)
25/07/2020 14

15. T(n) = 1
Solution:
T(n) = T(n –1) + b
T(n –1) = T(n –2) + b
Substituting (2) in (1)
T(n) = T(n –2) + b + b
T(n) = T(n –2) + 2b
T(n –2) = T(n –3) + b
Substituting (4) in (3)
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)+bn >1
25/07/2020 15

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

17. .
.
T(n) = 2
n–1
+ (2
n–1
–1)b
T(n) = 2
n–1
(b + 1) –b
= 2
n
(b + 1)/2 –b Let c
= (b + 1)/2 T(n) = c 2
n
–b
= O(2
n
)
4. T(n) = T(n/2) + b
T(1) = 1
Solution:
T(n) = T(n/2) + b
T(n/2) = T(n/4) + b
Substituting (2) in (1)
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

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

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

20. 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 > 0and n ≥ n
0
•Inductionhypothesis: T(k) ≤ d g(k) for all k < n
•Prove the induction goal
•Use the induction hypothesisto find some values of the
constants d andn
0for which the induction goalholds
2025/07/2020

21. Example: Binary Search
T(n) = c + T(n/2)
•Guess: T(n) = O(lgn)
•Induction goal: T(n) ≤ d lgn, for some dand n ≥ n
0
•Inductionhypothesis: 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

22. Example 2
T(n) = T(n-1) + n
•Guess: T(n) = O(n
2
)
•Induction goal: T(n) ≤ c n
2
, for some cand n ≥ n
0
•Inductionhypothesis: T(k-1) ≤ c(k-1)
2
for all k <n
•Proof of induction goal:
T(n) = T(n-1) + n ≤ c (n-1)
2
+ n
= cn
2
–(2cn –c -n) ≤ cn
2
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

23. Example 3
T(n) = 2T(n/2) + n
•Guess: T(n) = O(nlgn)
•Induction goal: T(n) ≤ cn lgn, for some cand n ≥ n
0
•Inductionhypothesis: T(n/2) ≤ cn/2 lg(n/2)
•Proof of induction goal:
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

24. Changing variablesn
•Rename: m = lgnn = 2
m
T (2
m
) = 2T(2
m/2
) + m
•Rename: S(m) = T(2
m
)
S(m) = 2S(m/2) + m S(m) = O(mlgm)
(demonstrated before)
T(n) = T(2
m
) = 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

25. 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

26. 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 guessesfor the substitution
method.
•The recursion-tree method can be
unreliable.
•The recursion-tree method promotes
intuition, however.
25/07/2020 26

27. 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/(2
d
)
the size parameter converging to base case, i.e. case 1
such that, n/(2
d
) = 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

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

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

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

31. Example of recursion tree
Solve T(n) = T(n/4) + T(n/2)+ n
2
:
n
2
(n/4)
2
(n/2)
2
T(n/16)T(n/8)T(n/8)T(n/4)
25/07/2020 31

32. Example of recursion tree
(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)+ n
2
:
n
2
25/07/2020 32

33. Example of recursion tree
Solve T(n) = T(n/4) + T(n/2)+ n
2
:
(n/16)
2
(n/8)
2
(n/8)
2
(n/4)
2
(n/4)
2
(n/2)
2
Q(1)2n
n
2
25/07/2020 33

34. Example of recursion tree
Solve T(n) = T(n/4) + T(n/2)+ n
2
:
(n/16)
2
(n/8)
2
(n/8)
2
(n/4)
2
(n/4)
2
(n/2)
2
Q(1)2
16
5
n 2n
n
2
25/07/2020 34

35. Example of recursion tree
Solve T(n) = T(n/4) + T(n/2)+ n
2
:
(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
n
2
(n/2)
2
…
25/07/2020 35

36. Example of recursion tree
Solve T(n) = T(n/4) + T(n/2)+ n
2
:
(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
5
2
16
5
16
52
n
…
Total =
= Q(n
2
)
n
2
(n/2)
2
geometric series
25/07/2020 36

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

38. 25/07/2020 38

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

40. 25/07/2020 40

41. 25/07/2020 41

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

43. 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/bmay not be an integer, but we ignore floors and ceilings.
•Requires memorization of three cases.
25/07/2020 43

44. The Master Theorem
Theorem 4.1
Let a 1and b> 1be 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/bby n/bor n/b.
T(n) can be bounded asymptotically in three cases:
1.If f(n) = O(n
logba–
)for some constant > 0, then T(n) = Q(n
logba
).
2.If f(n) = Q(n
logba
), then T(n) = Q(n
logba
lg n).
3.If f(n) = (n
logba+
)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

45. Master Method –Examples
•T(n) = 16T(n/4)+n
•a = 16, b= 4, n
logba
= n
log416
= n
2
.
•f(n) = n= O(n
logba-
) = O(n
2-
), where = 1 Case 1.
•Hence, T(n) = Q(n
logba
) = Q(n
2
).
•T(n)= T(3n/7)+ 1
•a = 1, b=7/3, andn
logba
= n
log7/31
= n
0
= 1
•f(n) = 1= Q(n
logba
)Case 2.
•Therefore,T(n)= Q(n
logba
lgn)= Q(lgn)
25/07/2020 45

46. Master Method –Examples
•T(n)= 3T(n/4)+ n lgn
•a = 3, b=4, thusn
logba
= n
log43
= O(n
0.793
)
•f(n)= n lgn = (n
log43+ 
)where 0.2Case 3.
•Therefore,T(n)= Q(f(n))= Q(n lgn).
•T(n)= 2T(n/2)+ n lgn
•a = 2, b=2, f(n)= n lgn, and n
logba
= n
log22
= n
•f(n)is asymptotically larger thann
logba
, but not
polynomially larger. The ratio lgnis asymptotically less than
n

for any positive . Thus, the Master Theorem doesn’t
apply here.
25/07/2020 46

47. Master Method –Examples
T(n) = 9T(n/3) + n
a=9, b=3, f(n) =n
n
logba
= n
log39
=Q(n
2
)
Since f(n) = n, f(n)< n
logba
Case 1applies:
T(n)Qn
log
bawhenf(n)On
log
ba
Thus the solution is T(n) =Q(n
2)
25/07/2020

48. Problems onThe MasterMethod
T(n) = 4T(n/2) +n
2
a = 4, b = 2,f(n)=n
2
n
logba =n
2
Since, f(n)=n
2
Thus, f(n)=n
logba
Case 2applies:
f (n) =Q(n
2logn)
Thus the solution is T(n) = Q(n
2logn).
25/07/2020

49. Master Method –Examples




Ex. T(n) = 4T(n/2) + n
3
a = 4, b = 2, f(n)=n
3 n
logba
= n
2; f (n) = n
3.
Since, f(n)=n
3 Thus, f(n)> n
logba
Case 3applies:
f (n) =(n
3)
and 4(n/2)
3 cn
3 (regulatory condition) for c =1/2.
T(n) =Q(n
3).
25/07/2020

50. 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 = log22
2
= 2 log22 = 2
n
log a
= n
2
b
Master Method –Examples
25/07/2020 50

51. f(n) = O(n
2
)
n = O(n
2
)It will fall in Case 1. So that
T(n) = (n
2
)
2. T(n) = 4T(n/2) + n
2
n > 1 T(n) = 1n = 1
From the above recurrence relation we obtain a = 4, b = 2, c = 1, d = 1, f(n) =
n
2
n
log a
= n
2
b
f(n) = n
2
) n
2
= (n
2
)
It will fall in case 2.
T(n) = (n
2
log n)
3. T(n) = 4T(n/2) + n
3
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
3
n
log a
= n
3
b
f(n) = Ω(n
log
b
a + €)
Master Method –Examples
25/07/2020 51

52. 25/07/2020 52

53. Examples
25/07/2020 53

54. Examples
25/07/2020 54

55. Master Method –Examples
25/07/2020 55

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