Analysis and Design of Algorithms
• Recurrence Relations
• Recursion
copyright - Design and Analysis of Algorithms
Dr. Debopam acharya
Contents
◼ After completion of this presentation, you will be able to
Understand the concept of recursion as a strategy for divide and conquer
Understand recurrence relations
2
Recurrence Relations
◼ Many algorithms, particularly divide and conquer algorithms, have time
complexities which are naturally modeled using recurrence relations.
◼ A recurrence relation is an equation which is defined in terms of itself.
3
Recurrence Relations
◼ Many natural functions can be easily expressed as recurrence relations. Some
examples are given below:
4
Recursion can be solved by Mathematical Induction
◼ In both these concepts, we have general and boundary conditions, with the general
condition breaking the larger problem into smaller problems.
◼ The initial or boundary condition terminate the recursion.
◼ As we will see, induction provides a useful tool to solve recurrences - guess a
solution and prove it by induction. However, to solve the problem in shorter time,
the guess must be strong !
5
Techniques for solving Recurrence Relations
Techniques for solving Recurrence Relations
Induction proofs
Master Theorem
6
Techniques for solving Recurrence Relations
◼ No general, automatic procedure for solving recurrence relations is known.
◼ There are methods for solving specific forms of recurrences.
◼ For such recurrences, we will now see both the approaches,
Induction, and
Master Theorem
7
Induction Approach
Tn = 2Tn-1 + 1 ; T0 = 0
Prove: Tn = 2n - 1 by induction:
Solution:
1. Base Case: n=0: T0 = 20 - 1 = 0
2. Inductive Hypothesis (IH): Tn = 2n – 1 for n ≥ 0
3. Inductive Step: Show Tn+1 = 2n+1 – 1 for n ≥ 0
Tn+1 = 2Tn + 1
= 2 ( 2n - 1 ) + 1 (applying IH)
= 2n+1 -1
8
Example: Merge sort analysis
Mergesort(array)
n = size(array)
if ( n = = 1) return array
array1 = Mergesort(array[1 .. n/2])
array2 = Mergesort(array[n/2 + 1 .. n])
return Merge(array1, array2)
Recurrence relation for Merge Sort will be: T(n) = 2T( n/2 ) + n , T(1) = 1
9
Merge Sort Induction Proof
Prove that T(n) = 2T( n/2 ) + n , T(1) = 1 is O(n lg n).
Prove that T(n) ≤ c n lg n , for all n greater than some value.
Base cases:
T(2) = 4 ≤ c 2 lg 2
T(3) = 5 ≤ c 3 lg 3
c ≥ 2 suffices
Inductive Hypothesis: T(n/2 ) ≤ c (n/2 ) lg (n/2 ) for n ≥ ?
Inductive Step: Show that T(n) ≤ c n lg n for n ≥ ?
10
Merge Sort Induction Proof
Given : T(n/2 ) ≤ c (n/2 ) lg (n/2 )
T(n) = 2T( n/2 ) + n
≤ 2( c(n/2) lg (n/2) ) + n (applying IH)
≤ 2( c(n/2) lg (n/2) ) + n (dropping floors makes it bigger!)
≤ c n lg(n/2) + n
≤ c n ( lg(n) - lg(2) ) + n
≤ c n lg(n) - c n + n (lg 2 = 1)
≤ c n lg(n) - (c - 1) n
< c n lg(n) (c > 1)
11
Some complications that might come in the way
◼ The next example illustrates one complication that can arise.
◼ Solve T(n)= 2 T(n/2) + 1
Guess T(n) =O(n) => T(n)<=c*n
T(n)= 2 T(n/2) + 1
<= 2c*n/2 + 1
<= cn+1
◼ We need to reach the conclusion that T (n) <= c*n , and to do this we must
determine a number c such that c*n +1 <=c*n .
◼ But this inequality is obviously false for all positive c. Apparently the induction
step cannot be made to work, which might lead us to believe that our guess is
incorrect.
12
Master Method
◼ It can be tedious and difficult to work out some recurrences. The master method
provides a way to generalize the asymptotic qualities of recurrences of the form:
T(n) = aT (n/b) + cnk where a, c, k > 0, b > 1.
◼ If you memorize three cases, most recurrences are solved very quickly.
13
Master Method
14
Master Method
15
Examples of the Master Theorem
◼ T(n) = 4 T(n/2) + n
Reading from the equation, a=4, b=2, and f(n) = n.
case 1 applies and
16
Examples of the Master Theorem
◼ T(n) = 4 T(n/2) + n2
Reading from the equation, a=4, b=2, and
Is ?
No, if , but it is true if so case 2 applies and
17
Examples of the Master Theorem
◼ T(n) = 4 T(n/2) + n3
Reading from the equation, a=4, b=2, and f(n) = n3
Is ?
Yes, for , so case 3 might apply.
Is 4(n/2)3 <=c.n3 ?
Yes, for c>= ½ , so there exists a c<1 to satisfy the regular condition,
so case 3 applies and T(n) = Θ(n3)
18
◼ In this presentation, we learnt
the concept of recursion as a strategy for divide and conquer
Learnt how to develop recurrence relation from a given code, and find their
complexities
recurrence relations and the two approaches to solve them
19
Introduction to Divide and Conquer
◼ Divide and conquer attempts to solve larger problems by dividing then into smaller
problems and apply the same strategy to solve these problems.
◼ An Example: Assume that a company asks it employees to spread a msg by calling
1 lakh people in a city. How will the company do it?
One option is to deploy 10000 tele-callers and ask them to call just 10 persons each, but
that would be costly.
Another options is to call 10 of their managers and delegate them this job. They will in
turn delegate this to 10 other employees. This delegation will continue until there are
employees who will end up calling 10 people to spread their msg.
20
Introduction to Divide and Conquer
◼ The below mentioned pseudocode explains the strategy:
void spread (int number_of_calls)
{
if (number_of_calls<=10)
{
call individual person to spread the msg)
else
{
find 10 employees
ask each of them to make (number_of_calls/10) phone calls.
compile the report of these employees
} }
}
21
Introduction to Divide and Conquer
◼ You may see that the nature of the problem is same, contacting x employees to
delegate so that each time the number of employees is reduced by a factor of 10.
◼ To implement this concept in programming this would mean you are calling the
function itself, each time reducing the problem by a factor ( in this case, a factor of
10)
22
Some examples
◼ How to implement a factorial of n ?
◼ n! = n * (n-1) * (n-2) * (n-3) … * 3 * 2 * 1, 0! =1
23
Some examples
◼ An iterative solution
int factorial(int n)
{
int x, y;
x = 1;
for ( y=n; y>=1; y--)
x = x*y;
return ( x );
}
24
Some examples
◼ A recursive solution
int factorial(int n)
{
if (n==0) return (1);
else return (n * factorial(n-1));
}
A step by step evaluation:
factorial (5) = 5 * factorial (4)
= 5 * 4 * factorial (3)
= 20 * 3 * factorial (2)
= 60 * 2 * factorial (1)
= 120 * 1 * factorial (0)
= 120
◼ This is called tracing of a recursive function
25
Some examples
◼ Exponentiation
◼ Xn = X * Xn-1
What would be a recursive algorithm to implement exponentiation?
26
Some examples
◼ Exponentiation
◼ Xn = X * Xn-1
int powerX( int X, int n)
{
if (n==0) return 1;
if (n==1) return X;
else return x * powerX( X , n–1 );
}
27
Some examples
◼ Exponentiation – another version
◼ Xn = (X2)n/2 if n is even
◼ = (X2)n/2 * X if n is odd
int powerX( int X, int n)
{
if ( n==0) return 1;
if(n==1) return X;
if (n is even) return powerX( X * X, n/2);
else return powerX( X * X, n/2 ) * X ;
}
Which has better time complexity between the two approaches, and how do we prove it?
28
Time Complexity Analysis of Recursive Functions
◼ Let's take both the versions of Exponentiation:
◼ Xn = X * Xn-1 ◼ Xn = (X2)n/2 if n is even
◼ = (X2)n/2 * X if n is odd
int powerX( int X, int n) int powerX( int X, int n)
{ {
if (n==0) return 1; if ( n==0) return 1;
if (n==1) return X; if(n==1) return X;
else return X * powerX( X , n–1 ); if (n is even) return powerX( X * X, n/2);
} else return powerX( X * X, n/2 ) * X ;
}
29
Time Complexity Analysis of Recursive Functions
◼ Xn = X * Xn-1
int powerX( int X, int n)
{
if (n==0) return 1;
if (n==1) return X;
else return X * powerX( X , n–1 );
}
At every trace, this problem’s size reduces by 1, and at every trace 2
arithmetic operations are involved (one multiplication and one subtraction).
Also, when n=1, we need just 1 operation. Hence,
T(n) = T(n-1) + 2,
T(1) =1
30
Time Complexity Analysis – Recursive Functions
◼ To solve T(n) = T(n-1) + 2, T(1) =1, we can see that
T(n – 1 ) = T(n – 2 ) + 2
Implies T(n ) = T(n – 2 ) + 2 (2)
T(n ) = T(n – 3 ) + 2 (3)
Hence, we can write:
T(n ) = T(n – k ) + 2(k)
We can also see that T(1) =1
Let us set n-k =1 (we want to eliminate the T(n-k) term)
Hence k = n-1
This implies
T(n) = T(1) + 2(n – 1 )
and so, T(n) = 2n– 1
Implies T(n) = O(n)
31
Time Complexity Analysis – Recursive Functions
◼ Xn = (X2)n/2 if n is even
◼ = (X2)n/2 * X if n is odd
int powerX( int X, int n)
{
if ( n==0) return 1;
if(n==1) return X;
if (n is even) return powerX( X * X, n/2);
else return powerX( X * X, n/2 ) * X ;
}
Each time, it gets reduced by half, and the maximum operations that takes
place in each step is 3
Hence, T(n) = T(n/2) + 3, T(1) = 1
32
Time Complexity Analysis – Recursive Functions
To solve T(n) = T(n/2) + 3 , T(1) =1, we can see that
T(n/2) = T(n/4) + 3
T(n) = T(n/4) + 3(2)
= T(n/8) + 3(3)
…
implies T(n) = T( n/ 23 ) + 3(3)
or T(n) = T( n/ 2k) + 3(k)
As T(1) =1, lets try some substitution that would make this possible.
Let 2k = n then k = log(n)
Then T(n) = T(1) + 3 log(n)
Which implies T(n) = O(logn) .
So this version of our approach of implementing exponentiation has better
complexity!
33
Some examples
Algorithm Method1(A[1..n], B[1..n], C[1..n]);
if n= 0 then return;
For i := 1 to n do
C[1] := A[1] * B[i];
call Method1(A[2..n], B[2..n], C[2..n]);
Find T(n) and solve it to find the complexity.
34
Some examples
Algorithm Method1(A[1..n], B[1..n], C[1..n]);
if n= 0 then return;
For i := 1 to n do
C[1] := A[1] * B[i];
call Method1(A[2..n], B[2..n], C[2..n]);
Ans: T(n) = T(n-1) + O(n)
= (T(n-2) + O(n-1)) + O(n)
= T(n-2) + O(n-1) + O(n)
= T(n-3) + O(n-2) + O(n-1) + O(n)
...
= T(1) + O(2) + ... + O(n-1) + O(n)
= O(1 + 2 + ... + n-1 + n)
= O(n^2)
35
Some examples
int m1(int A[ ], int n)
{
if(n < 1)
return 0;
else
return A[n-1]%2 + m1( A, n-1);
}
Find T(n)?
36
Some examples
int m1(int A[ ], int n)
{
if(n < 1)
return 0;
else
return A[n-1]%2 + m1( A, n-1);
}
T(n) = T(n-1) + 4, T(1) = 1;
37
Some examples
int m1(int a, int n)
if(n == 1) return 0;
else return a + m1(a,n-1) * m1(a,n-1);
Find T(n)
38
Some examples
int m1(int a, int n)
if(n == 1) return 0;
else return a + m1(a,n-1) * m1(a,n-1);
T(n) = 2T(n-1) + 3, T(1) = 1;
39
