2CS503 Design & Analysis

Unit-3of Algorithm
Divide and Conquer
Algorithm
Recurrence Relation
Topics to be covered
▪ Introduction to Recurrence Equation
▪ Different methods to solve recurrence
▪ Divide and Conquer Technique
▪ Multiplying large Integers Problem
▪ Problem Solving using divide and conquer algorithm –
1. Binary Search
2. Sorting (Merge Sort, Quick Sort)
3. Matrix Multiplication
4. Exponential

2
Introduction
▪ Many algorithms (divide and conquer) are recursive in nature.
▪ When we analyze them, we get a recurrence relation for time complexity.
▪ We get running time as a function of 𝒏 (input size) and we get the running time on inputs
of smaller sizes.
▪ A recurrence is a recursive description of a function, or a description of a function in
terms of itself.
Or
▪ A recurrence is an equation or inequality that describes a function in terms of its values
on smaller inputs.
Or
▪ A recurrence relation is an equation that defines a sequence based on a rule that gives the
next term as a function of the previous term(s)

3
Methods to Solve Recurrence
▪ Substitution
▪ Homogeneous (characteristic equation)
▪ Non-homogeneous
▪ Master method
▪ Recurrence tree
▪ Intelligent guess work
▪ Change of variable
▪ Range transformations

4
Substitution Method
▪ We make a guess for the solution and then we use mathematical induction to prove the
guess is correct or incorrect.
▪ Example 1:
𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑛 1

▪ Replacing 𝑛 by 𝑛 − 1 and 𝑛 − 2, we can write following equations.

𝑇(𝑛 − 1) = 𝑇(𝑛 − 2) + 𝑛 − 1 2

𝑇(𝑛 − 2) = 𝑇(𝑛 − 3) + 𝑛 − 2 3
▪ Substituting equation 3 in 2 and equation 2 in 1 we have now,
𝑇(𝑛) = 𝑇(𝑛 − 3) + 𝑛 − 2 + 𝑛 − 1 + 𝑛 4

5
Substitution Method
𝑇(𝑛) = 𝑇(𝑛 − 3) + 𝑛 − 2 + 𝑛 − 1 + 𝑛 4

▪ From above, we can write the general form as,

𝑇 𝑛 = 𝑇 𝑛 − 𝑘 + (𝑛 − 𝑘 + 1) + (𝑛 − 𝑘 + 2) + … + 𝑛

▪ Suppose, if we take 𝑘 = 𝑛 then,

𝑇(𝑛) = 𝑇(𝑛 − 𝑛) + 𝑛 − 𝑛 + 1 + 𝑛 − 𝑛 + 2 + … + 𝑛

𝑇 𝑛 = 0 + 1 + 2 + …+ 𝑛

𝑛 𝑛+1
𝑇 𝑛 = = 𝑶 𝒏𝟐
2
6
Exercise 1
𝑐1 𝑖𝑓 𝑛 = 0
𝑡 𝑛 =ቊ
𝑐2 + 𝑡 𝑛 − 1 𝑜/𝑤
Rewrite, 𝑡 𝑛 = 𝑐2 + 𝑡(𝑛 − 1)
Now, replace 𝑛 by 𝑛 – 1 and 𝑛 − 2
𝑡 𝑛 − 1 = 𝑐2 + 𝑡(𝑛 − 2)
𝑡 𝑛 − 2 = 𝑐2 + 𝑡(𝑛 − 3)
So,
𝑡 𝑛 = 𝑐2 + 𝑐2 + 𝑐2 + 𝑡(𝑛 − 3)
In general,
𝑡 𝑛 = 𝑘𝑐2 + 𝑡(𝑛 − 𝑘)
Suppose if we take 𝑘 = 𝑛 then,
𝑡 𝑛 = 𝑛𝑐2 + 𝑡 𝑛 − 𝑛 = 𝑛𝑐2 + 𝑡 0 = 𝑛𝑐2 + 𝑐1 = 𝑶 𝒏

7
Exercise 2
▪ Solve the following recurrence using substitution method.
1 𝑖𝑓 𝑛 = 0 𝑜𝑟 1
𝑇 𝑛 =ቊ
𝑇 𝑛 − 1 + 𝑛 − 1 𝑜/𝑤

8
Solving recurrence relation
• Iteration (already discussed in previous slides)
• Characteristics root
• Generating function

9
Homogeneous Recurrence
Recurrence equation
𝑎0 𝑇(𝑛) + 𝑎1 𝑇(𝑛 − 1) + 𝑎2 𝑇(𝑛 − 2) + ⋯ + 𝑎𝑘 𝑇(𝑛 − 𝑘) = 𝑓(𝑛)
is called the recurrence of order k, where a0,a1,a2,…ak are constants; it is also known as kth
order linear recurrence relation.
▪ Homogeneous Recurrence equation
𝑎0 𝑇(𝑛) + 𝑎1 𝑇(𝑛 − 1) + 𝑎2 𝑇(𝑛 − 2) + ⋯ + 𝑎𝑘 𝑇(𝑛 − 𝑘) = 0
▪ The equation of degree 𝑘 in 𝑥 is called the characteristic equation of the recurrence,
𝑝 𝑥 = 𝑎0 𝑥 𝑘 + 𝑎1 𝑥 𝑘−1 + ⋯ + 𝑎𝑘 𝑥 0 {order=n-(n-k)=>k i.e. difference between highest and lowest}

10
Homogeneous Recurrence
▪ Find the equation in terms of x, i.e., characteristic equation.
▪ Solve the characteristics equation and find the characteristic root.
▪ If characteristic roots are:
• r = r1, r2, r3 distinct => Sol: T(n) = c1.r1n + c2.r2n + c3.r3n
• r = r1 , r1 same => Sol: T(n) = (c1+n.c2)r1n 𝑡𝑛 = σ𝑘𝑖=1 𝑐𝑖 𝑟𝑖𝑛
• r = r1, r1, r2, r3 => Sol: T(n) = (c1+n.c2)r1n + c3.r2n + c4.r3n
• r = r1, r1, r1, r2 => Sol: T(n) = (c1+n.c2+n2.c3)r1n + c4.r2n

11
Example
▪ T(n)= T(n-1) + 2 T(n-2) , n>=2, T(0) = 0, T(1) = 1
▪ T(n) - T(n-1) - 2 T(n-2) = 0
▪ 𝑥2 − 𝑥 − 2 = 0
▪ 𝑥 = 2, −1
▪ T(n) = c1.2n + c2.(-1)n
▪ T(0) = 0, c1 + c2=0
▪ T(1) = 1, 2.c1 - c2=1
▪ c1= 1/3, c2= -1/3

▪ T(n)= 4(T(n-1) - T(n-2)) , n>=2, T(0) = 1, T(1) = 1

12
Analysis: Fibonacci series
Function fibiter(n)
i ← 1; j ← 0;
for k ← 1 to n do
j ← i + j;
i ← j – i;
return j

Iterative Algorithm for Fibonacci series: If we count all arithmetic

operations at unit cost; the instructions inside for loop take constant
time 𝑐. The time taken by the for loop is bounded above by 𝑛, 𝑖. 𝑒.,
𝒏𝒄 = 𝛉(𝒏)

13
Analysis: Fibonacci series
▪ Recursive Algorithm for Fibonacci series,

Function fibrec(n)
if n < 2 then return n
else return fibrec (n – 1) + fibrec (n – 2)

▪ The recurrence equation of above algorithm is given as,

𝑛 𝑖𝑓 𝑛 = 0 𝑜𝑟 1
𝑇(𝑛) = ቊ
𝑇 𝑛 − 1 + 𝑇 𝑛 − 2 𝑜/𝑤
▪ The recurrence can be re-written as,
𝑇 𝑛 −𝑇 𝑛−1 −𝑇 𝑛−2 =0

14
Analysis: Fibonacci series
▪ The characteristic polynomial is,
𝑥2 − 𝑥 − 1 = 0 −𝑏 ± 𝑏2 − 4𝑎𝑐
𝑥 =
2𝑎
▪ Whose roots are,
1+ 5 1− 5
𝑟1 = and 𝑟2 =
2 2
▪ The general solution is therefore of the form,
𝒌
𝑻𝒏 = 𝒄𝟏 𝒓𝒏𝟏 + 𝒄𝟐 𝒓𝒏𝟐
𝒕𝒏 = ෍ 𝒄𝒊 𝒓𝒏𝒊
▪ Substituting initial values 𝑛 = 0 and 𝑛 = 1 𝒊=𝟏
𝑇0 = 𝑐1 + 𝑐2 = 0 1
𝑇1 = 𝑐1 𝑟1 + 𝑐2 𝑟2 = 1 (2)

15
Analysis: Fibonacci series
▪ Solving these equations, we obtain
1 1
𝑐1 = and 𝑐2 = −
5 5
▪ Substituting the values of roots and constants,
𝑛 𝑛
1 1+ 5 1− 5
𝑇𝑛 = − … … … de Moivre′ s formula
5 2 2

𝑻𝒏 ∈ 𝑶 ∅ 𝒏

▪ Time taken for recursive Fibonacci algorithm grows exponentially.

16
Analysis: Tower of Hanoi

17
Analysis: Tower of Hanoi

18
Analysis: Tower of Hanoi
▪ The number of movements of a ring required in the tower of Hanoi problem is given by,
0 𝑖𝑓 𝑚 = 0
𝑡 𝑚 = ቊ
2𝑡 𝑚 − 1 + 1 𝑜/𝑤
▪ The equation can be written as,
𝑡 𝑚 − 2𝑡 𝑚 − 1 = 1 (1)
▪ To convert it into homogeneous equation,
• Multiply with -1 and replace m by m-1,
−𝑡 𝑚 − 1 + 2𝑡 𝑚 − 2 = −1 (2)
▪ Solving equations (1) and (2), we have now
𝒕 𝒎 − 𝟑𝒕 𝒎 − 𝟏 + 𝟐𝒕(𝒎 − 𝟐) = 𝟎

19
Analysis: Tower of Hanoi
▪ The characteristic polynomial is,
𝑥 2 − 3𝑥 + 2 = 0
▪ Whose roots are,
𝑟1 = 2 and 𝑟2 = 1
▪ The general solution is therefore of the form,
𝑡𝑚 = 𝑐1 1𝑚 + 𝑐2 2𝑚
▪ Substituting initial values m= 0 and m= 1
𝑡0 = 𝑐1 + 𝑐2 = 0 1
𝑡1 = 𝑐1 + 2𝑐2 = 1 (2)
▪ Solving these linear equations we get c1 = -1 and c2 = 1.
▪ Therefore time complexity of tower of Hanoi problem is given as,
𝒕 𝒎 = 𝟐𝒎 − 𝟏 = 𝑶 𝟐𝒎

20
Non-homogeneous recurrence
Recurrence equation
𝑎0 𝑇(𝑛) + 𝑎1 𝑇(𝑛 − 1) + 𝑎2 𝑇(𝑛 − 2) + ⋯ + 𝑎𝑘 𝑇(𝑛 − 𝑘) = 𝑓(𝑛)
is called as recurrence of order k, where a0,a1,a2,…ak are constants, it is also known as kth
order linear recurrence relation.
The solution of a given recurrence relation is given by:
Total solution or general solution := Homogeneous solution + Particular solution
T(n) = T(n)h+T(n)p

Homogeneous solution(T(n)h): we calculate homogeneous solution by putting f(n)=0,

and simply solves it.
T(n)h => 𝑎0 𝑇(𝑛) + 𝑎1 𝑇(𝑛 − 1) + 𝑎2 𝑇(𝑛 − 2) + ⋯ + 𝑎𝑘 𝑇(𝑛 − 𝑘) = 0

21
Particular solution(T(n)p): it exist only when RHS of recurrence relation is non-zero. i.e.
f(n)≠0.
If f(n)≠0 we consider three possibility:
• Case1: f(n) is constant
• Case2: f(n) is polynomial of degree n
• Case3: f(n) is exponential

22
Particular solution(T(n)p) T(n)-2T(n-1)+T(n-2)=1

Case1: f(n) is constant => To calculate Particular solution

1. find p by putting T(n)=p,
=> put T(n)=P
2. If fails, put T(n)=np => P-2(P-1)+P-2=1
3. If fails, put T(n)=n2p… => 0=1 fail

=> put T(n)=nP

=> nP-2(n-1)P+(n-2)P=1
=> 0=1 fail

=> put T(n)=n2P

=> n2P – 2(n-1)2P+(n-2)2P=1
=> p=1/2
=> Now put the value of P in solution
T(n)p=n2P=>n2/2

23
Particular solution(T(n)p) T(n)-8T(n-1) =14n+5

Case2: f(n) is polynomial => To calculate Particular solution

1. T(n)=d0+d1n+d2n2…dmnm
=> put T(n)= d0+d1n
2. Find d0, d1, d2.. by comparing => d +d n – 8(d +d (n-1))=14n+5
0 1 0 1
the co-efficient => -7d0 – 7d1n+8d1=5 + 14n
=> By comparing the coefficient of n0, n1 term
=> -7d1=14 => d1=-2
=> -7d0+8d1=5 =>d0= -3
Now put the value of d0 and d1 to get the solution
T(n)p=d0+d1n
T(n)p= -3 + (-2)n

24
Particular solution(T(n)p) T(n)-8T(n-1) =5 * 2n

Case3: f(n) is exponential function => To calculate Particular solution

find d by putting T(n)=d*an,
=> put T(n)= dan {a=2}
find d by putting T(n)= (d0+d1n) an => d*2n – 8*d2n-1=5*2n
if f(n) contain 1 order polynomial => d*2n – 4*21*d2n-1=5*2n
=> d*2n – 4*d2n=5*2n
=>2n(d-4d)=5*2n
if homogeneous solution contains a term ak => By comparing the coefficient of 2n
then T(n)= n(d*an) => d=-5/3
if contain two times then Now put the value of d to get the solution
T(n)p=dan
T(n)= n2(d*an) T(n)p= -5/3* 2n

25
Find the total solution: T(n)-8T(n-1) =14n+5
1. Homogeneous solution(T(n)h) 2. Particular solution(T(n)p)
T(n)-8T(n-1)=0 ▪ => put T(n)= d0+d1n
characteristic equation ▪ => d0+d1n – 8(d0+d1(n-1))=14n+5
X-8=0 , roots=(8) ▪ => -7d0 – 7d1n+8d1=5 + 14n
T(n)h = c18n ▪ => By comparing the coefficient of n0, n1
term
▪ => -7d1=14 => d1=-2
▪ => -7d0+8d1=5 =>d0= -3
▪ Now put the value of d0 and d1 to get the
solution
▪ T(n)p=d0+d1n
▪ T(n)p= -3 + (-2)n

Total solution(T(n))=(T(n)h) + (T(n)h)

T(n) = c18n -3 + (-2).n

26
Master Method(for divide and conquer recurrence)
▪ All divide and conquer algorithm divide the problem into sub-problems, each of which is part of
the original problem, and then perform some additional work to compute the final answer..
▪ Suppose you have a recurrence of the form
Time to divide &
recombine
𝑇(𝑛) = 𝑎𝑇(𝑛/𝑏) + 𝑓(𝑛)

Number of sub- Time required to

problems solve a sub-problem

▪ This recurrence would arise in the analysis of a recursive algorithm.

▪ When input size 𝑛 is large, the problem is divided up into 𝑎 sub-problems each of size 𝑛/𝑏. Sub-
problems are solved recursively and results are recombined.
▪ The work to split the problem into sub-problems and recombine the results is 𝑓(𝑛).

27
Master Method(for divide and conquer recurrence)
As an example, a merge sort algorithm operates on two sub-problems, each of which is
half the size of the original, and then performs O(n) additional work for merging. This gives
the running time equation:
T(n) = 2T (n/2) + O(n)

The following theorem can be used to determine the running time of divide and
conquer algorithms. For a given program (algorithm), first we try to find the recurrence
relation for the problem. If the recurrence is of the below form, then we can directly give the
answer without fully solving it. If the recurrence is of the form

28
Master Method(for divide and conquer recurrence)

where a ≥ 1, b >1, k ≥ 0 and p is a real number, then:

29
1.

30
2.

31
3.

32
4.

33
5.

34
6.

35
7.

36
8.

37
9.

38
10.

We can not apply master method in such cases

39
Master Method
▪ Example 4: 𝑇(𝑛) = 4𝑇(𝑛/2) + 𝑛2
▪ Example 5: 𝑇(𝑛) = 4𝑇(𝑛/2) + 𝑛3
▪ Example 6: 𝑇(𝑛) = 9𝑇(𝑛/3) + 𝑛
▪ Example 7: 𝑇(𝑛) = 𝑇(2𝑛/3) + 1
▪ Example 8: 𝑇 𝑛 = 7𝑇 𝑛Τ2 + 𝑛3
▪ Example 9: 𝑇(𝑛) = 27𝑇(𝑛2 ) + 16𝑛

40
Master Theorem for Subtract and Conquer
Recurrences
Let T(n) be a function defined on positive n, and having the property

𝑐 𝑖𝑓 𝑛 ≤ 1
T(n)= ቊ
𝑎𝑇 𝑛 − 𝑏 + 𝑓 𝑛 𝑖𝑓 𝑛 > 1
for some constants c,a > 0,b ≥ 0,k ≥ 0, and function f(n). If f(n) is in O(nk ), then

41
Recurrence Tree Method
Steps to solve recurrence relations using recursion tree method:

Step-01: Draw a recursion tree based on the given recurrence relation.

Step-02: Determine-
o Cost of each level
o Total number of levels in the recursion tree
o Number of nodes in the last level
o Cost of the last level

Step-03: Add cost of all the levels of the recursion tree and simplify the expression to
obtained in terms of asymptotic notation

42
Recurrence Tree Method
▪ Here while solving recurrences, we divide the problem into sub-problems of equal size.
▪ E.g., 𝑇(𝑛) = 𝑎 𝑇(𝑛/𝑏) + 𝑓(𝑛) where 𝑎 > 1 , 𝑏 > 1 and 𝑓(𝑛) is a given function.
▪ 𝐹(𝑛) is the cost of splitting or combining the sub problems.

𝑛 Τ𝑏 𝑛 Τ𝑏

43
Recurrence Tree Method
▪ Example 1: 𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑛
▪ The recursion tree for this recurrence is :

𝑛 Τ2 𝑛 Τ2 𝑛
log2 𝑛

𝑛 Τ22 𝑛 Τ22 𝑛 Τ22 𝑛 Τ22 𝑛

1 1 1 1 1
44
Step-01:
• Draw a recursion tree based on the given recurrence relation.
• The given recurrence relation shows-
• A problem of size n will get divided into 2 sub-problems of size n/2.
• Then, each sub-problem of size n/2 will get divided into 2 sub-problems of size n/4 and so on.
• At the bottom most layer, the size of sub-problems will reduce to 1.
The given recurrence relation shows-
• The cost of dividing a problem of size n into its 2 sub-problems and then combining its solution is n.
• The cost of dividing a problem of size n/2 into its 2 sub-problems and then combining its solution is n/2 and so on.

Step-02:
• Determine cost of each level-
• Cost of level-0 = n
• Cost of level-1 = n/2 + n/2 = n
• Cost of level-2 = n/4 + n/4 + n/4 + n/4 = n and so on.

45
Step-03:
• Determine total number of levels in the recursion tree-
• Size of sub-problem at level-0 = n/20
• Size of sub-problem at level-1 = n/21
• Size of sub-problem at level-2 = n/22
• Continuing in similar manner, we have- Size of sub-problem at level-i = n/2i
• Suppose at level-x (last level), size of sub-problem becomes 1. Then- n / 2x = 1
• 2x = n
• Taking log on both sides, we get- xlog22 = log2n
• x = log2n
• ∴ Total number of levels in the recursion tree = log2n + 1
Step-04:
• Determine number of nodes in the last level-
• Level-0 has 20 nodes i.e. 1 node
• Level-1 has 21 nodes i.e. 2 nodes
• Level-2 has 22 nodes i.e. 4 nodes
• Continuing in similar manner, we have- Level-log2n, has 2log2n nodes i.e. n nodes

46
Step-05: Determine cost of last level-
Cost of last level = n x T(1) = θ(n)
Step-06:
Add costs of all the levels of the recursion tree and simplify the expression so obtained in terms of
asymptotic notation-

= n x log2n + θ (n)
= nlog2n + θ (n)
= θ (nlog2n)

47
Recurrence Tree Method
▪ When we add the values across the levels of the recursion tree, we get a value of 𝑛 for
every level.
▪ The bottom level has 2log 𝑛 nodes, each contributing the cost 𝑇(1).
▪ We have 𝑛 + 𝑛 + 𝑛 + …… log 𝑛 𝑡𝑖𝑚𝑒𝑠
log 𝑛−1
𝑇(𝑛) = σ𝑖=02 𝑛 + 2log 𝑛 𝑇(1)
𝑇 𝑛 = 𝑛 log 𝑛 + 𝑛
𝑻 𝒏 = 𝑶(𝒏 log 𝒏)

48
Recurrence Tree Method
▪ Example 2: 𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑐. 𝑛2
▪ The recursion tree for this recurrence is :

𝑛2

𝑛Τ2 2
𝑛 Τ2 2 1Τ2 𝑛2

𝑛 Τ4 2 𝑛 Τ4 2 𝑛 Τ4 2 𝑛 Τ4 2 1Τ2 𝑛2

𝑂 𝑛2
51
Recurrence Tree Method
▪ Sub-problem size at level 𝑖 is 𝑛Τ2𝑖
2
▪ Cost of problem at level 𝑖 Is 𝑛
Τ2𝑖
▪ Total cost,
log2 𝑛−1 𝑖
1
𝑇 𝑛 = 𝑛2 ෍ +𝑂 𝑛
2
𝑖=0
𝑇 𝑛 = 2𝑛2 + 𝑂 𝑛

𝑇 𝑛 = 𝑂 𝑛2

52
Recurrence Tree Method
▪ Example 3: 𝑇(𝑛) = 𝑇(𝑛/4) + 𝑇(3𝑛/4) + 𝑐. 𝑛
▪ Example 4: 𝑇(𝑛) = 3𝑇(𝑛/4) + 𝑐. 𝑛2
▪ Example 5: 𝑇(𝑛) = 𝑇(𝑛/4) + 𝑇(𝑛/2) + 𝑛2
▪ Example 6: 𝑇(𝑛) = 𝑇(𝑛/3) + 𝑇(2𝑛/3) + 𝑛

53
Method of Guessing and Confirming

“guess the answer; and then prove it correct by induction”

What if the given recurrence doesn’t seem to match with any of these (master theorem)
methods? If we guess a solution and then try to verify our guess inductively, usually either
the proof will succeed (in which case we are done), or the proof will fail (in which case the
failure will help us refine our guess).

54
Example

Let’s start by trying to prove an upper bound T(n) < cnlogn:

The last inequality assumes only that 1 ≤ c. .logn. This is correct if n is sufficiently large and for any
constant c, no matter how small. From the above proof, we can see that our guess is correct for the
upper bound.

55
Change of variable-Method
➢ There are many ways to solve a recurrence relation runtime. One way to do this is a
method called “change of variable”.
➢ Domain transformations can sometimes be used to substitute a function for the
argument of the relation and make it easier to solve.
➢ The idea is to select a function for S(m), when given T(n).

56
m=logn
Example
n=2m --> T(2m)= S(m)
2m=2log2n
2m=n
2m/2=2(log2n/2)
T(n)=2T 𝐧 +logn 2m/2=n1/2
Let’s rewrite the equation by substituting m=log n, and then plug it back in to the recurrence to get the
following:
T(2m)=2T(2m/2)+m
Now we will create a new function called ‘S’ that takes in a parameter ‘m’ such that S(m) = T(2m).
Which means : S(m) = 2T(2m/2)+m.
If S(m) = T(2m) then S(m-1) = T(2(m-1)) and S(m/2) = T(2(m/2)), so we can rewrite our function to get the
following:
S(m)=2S(m/2)+m
Using master theorem we can write the solution of recurrence ‘S’: O(mlogm).
This means that our original function ‘T’ belongs to O(log n * log ( log n) ), since we can simply replace ‘m’
with ‘log n’ because m=log n

57
Example
T(n)= 𝐧T( 𝐧) +n
=>First substitute n = 2m
T(2m)=2m/2T(2m/2)+2m
Now divide both side by 2m
T(2m) =2m/2T(2m/2)+2m
2m 2m 2m

T(2m) =2m/2T(2m/2) +1 T(2m) T(2m/2)

{ m = m/2 +1}
2m 2m 2 2

T(2m)
=>second substitution S(m)= 2m
S(m)=S(m/2)+1
By applying masters method we get : S(m)= log m
T(2m)
Now back substitution => 2m =log m
T(2m)=2m log m
Again back-substitute: T(n)=n log log n

58
▪ T(n)=3T(n/2) +n
Substitute n=2m
T(2m)=3T(2m/2)+2m
T(2m)=3T(2m-1)+2m
Substitute S(m)=T(2m)
S(m)=3S(m-1)=2m
S(m)-3S(m-1)=2m
By characteristic equation
(X-3)(X-2)
Solution of S(m)=c13m+c22m
By back substitution
T(n)=c13logn+c22logn
=c1nlog3+c2nlog2

59
Range transformation
▪ When we make a change of variable, we transform the domain of the recurrence.
▪ Instead, it may be useful to transform the range to obtain a recurrence in a form that we
know how to solve. Both transformations can sometimes be used together.

Consider the following recurrence, which defines T(n) when n is a power of 2.

T(n)=nT2(n/2)
The first step is a change of variable: n=2m, S(m)=T(2m)
T(2m)= 2m T2(2m/2)=> T2(2m-1)
S(m)=2m S2(m-1)
▪ At first glance, none of the techniques we have seen applies to this recurrence since it is
not linear; To transform the range, we create yet another recurrence by using U(m) to
denote log S(m).

60
S(m)=2m S2(m-1)
Substitute U(m)=log(S(m))
=log(2m S2(m-1))
=log2m + log S2(m-1)
=m+2log S(m-1)
=m+2U(m-1)
U(m)= m+2U(m-1)
U(m)-2U(m-1)=m
Solve this by applying Characteristic equation:

61
Divide & Conquer (D&C) Technique
▪ Many useful algorithms are recursive in structure: to solve a given problem, they call
themselves recursively one or more times.
▪ These algorithms typically follow a divide-and-conquer approach:
▪ The divide-and-conquer approach involves three steps at each level of the recursion:
1. Divide: Break the problem into several sub problems that are similar to the original problem
but smaller in size.
2. Conquer: Solve the sub problems recursively. If the sub problem sizes are small enough, just
solve the sub problems in a straightforward manner.
3. Combine: Combine these solutions to create a solution to the original problem.

62
D&C: Running Time Analysis
▪ The running-time analysis of such divide-and-conquer (D&C) algorithms is almost
automatic.
▪ Let 𝑔(𝑛) be the time required by D&C on instances of size 𝑛.
▪ The total time 𝒕(𝒏) taken by this divide-and-conquer algorithm is given by recurrence
equation,
𝑡 𝑛 = 𝑎 ∗ 𝑡 𝑛/𝑏 + g 𝑛
▪ The solution of equation is given as, 𝑇(𝑛) = 𝑎𝑇(𝑛/𝑏) + 𝑓(𝑛)

𝜃 𝑛𝑘 𝑖𝑓 𝑎 < 𝑏 𝑘
𝑡 𝑛 = 𝜃 𝑛𝑘 𝑙𝑜𝑔𝑛 𝑖𝑓 𝑎 = 𝑏 𝑘
𝜃 𝑛𝑙𝑜𝑔𝑏 𝑎 𝑖𝑓 𝑎 > 𝑏 𝑘
𝑘 is the power of 𝑛 in 𝑔(𝑛)
63