[go: up one dir, main page]
Scribd
Upload
62 views33 pages

MCA 301: Design and Analysis of Algorithms: Instructor Neelima Gupta Ngupta@cs - Du.ac - in

This document contains information about solving recurrences using different methods like substitution method, recursion tree method, and the Master theorem. It provides examples of using substitution method to solve recurrences like T(n) = 2T(n/2) + n and discusses issues like boundary conditions. It also explains solving recurrences using recursion trees, showing examples for recurrences like T(n) = 2T(n/2) + 1 and T(n) = T(n/3) + T(2n/3) + n. The document discusses analyzing the costs across different levels of the recursion tree to determine the overall cost.

Uploaded by

Er Umesh Thoriya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
62 views33 pages

MCA 301: Design and Analysis of Algorithms: Instructor Neelima Gupta Ngupta@cs - Du.ac - in

This document contains information about solving recurrences using different methods like substitution method, recursion tree method, and the Master theorem. It provides examples of using substitution method to solve recurrences like T(n) = 2T(n/2) + n and discusses issues like boundary conditions. It also explains solving recurrences using recursion trees, showing examples for recurrences like T(n) = 2T(n/2) + 1 and T(n) = T(n/3) + T(2n/3) + n. The document discusses analyzing the costs across different levels of the recursion tree to determine the overall cost.

Uploaded by

Er Umesh Thoriya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 33

MCA 301: Design and

Analysis of Algorithms
Instructor
Neelima Gupta
ngupta@cs.du.ac.in
Table Of Contents

Solving Recurrences
The Master Theorem
Recurrence Relations
Recurrences
• The expression:
 c n 1

T ( n)  
2T    cn n  1
 n
  2 
is a recurrence.
– Recurrence: an equation that describes a function in
terms of its value on smaller functions
Recurrence Examples

 0 n0  0 n0
s ( n)   s ( n)  
c  s (n  1) n  0 n  s (n  1) n  0

n 1 
 c  c n 1
 
T ( n)   T ( n)  
2T    c n  1
 n  n
  2  aT    cn n  1
 b
Solving Recurrences
• Substitution method
• Iteration method
• Master method
Solving Recurrences
• The substitution method (CLR 4.1)
– “Making a good guess” method
– Guess the form of the answer, then use
induction to find the constants and show that
solution works
– Examples:
• T(n) = 2T(n/2) + (n)  T(n) = (n lg n)
• T(n) = 2T(n/2) + n  ???
Solving Recurrences
• The substitution method (CLR 4.1)
– “Making a good guess” method
– Guess the form of the answer, then use
induction to find the constants and show that
solution works
– Examples:
• T(n) = 2T(n/2) + (n)  T(n) = (n lg n)
• T(n) = 2T(n/2) + n  T(n) = (n lg n)
• T(n) = 2T(n/2 )+ 17) + n  ???
Substitution method

• Guess the form of the solution .

• Use mathematical induction to find the constants and


show that the solution works .

The substitution method can be used to establish either upper


or lower bounds on a recurrence.
An example (Substitution method )
• T(n) = 2T(floor(n/2) ) +n
We guess that the solution is T(n)=0(n lg n).
i.e. to show that T(n) ≤ cn lg n , for some constant c> 0 and n ≥ m.

Assume that this bound holds for [n/2]. So , we get


T(n) ≤ 2(c floor (n/2) lg(floor(n/2))) + n
≤ cn lg(n/2) + n
= cn lg n – cn lg 2 + n
= cn lg n – cn + n
≤ cn lg n
where , the last step holds as long as c≥ 1.
• Boundary conditions :

Suppose , T(1)=1 is the sole boundary condition of the


recurrence .
then , for n=1 , the bound T(n)≤ c n lg n yields
T(1)≤ c lg1=0 , which is at odds with T(1)=1.
Thus ,the base case of our inductive proof fails to hold.

To overcome this difficulty , we can take advantage of the


asymptotic notation which only requires us to prove
T(n)≤c n lg n for n≥ m.
The idea is to remove the difficult boundary condition T(1)= 1
from consideration.
Thus , we can replace T(1) by T(2) as the base cases in the
inductive proof , letting m=2.
Contd....

From the recurrence , with T(1) = 1, we get


T(2)=4

We require T(2)≤ c 2 lg 2

It is clear that , any choice of c≥2 suffices for


the base cases
Are we done?
• Have we proved the case for n =3.
• Have we proved that T(3) ≤ c 3 lg 3.
• No. Since floor(3/2) = 1 and for n =1, it does not hold. So
induction does not apply on n= 3.
• From the recurrence, with T(1) = 1, we get T(3) = 5.
The inductive proof that T(n) ≤ c n lg n for some constant c≥1
can now be completed by choosing c large enough that
T(3)≤c 3 lg 3 also holds.
It is clear that , any choice of c ≥ 2 is sufficient for this to hold.
Thus we can conclude that T(n) ≤ c n lg n for any c ≥ 2 and n ≥ 2.
Wrong Application of induction

Given recurrence: T(n) = 2T(n/2) + 1


Guess: T(n) = O(n)
Claim : Ǝ some constant c and n0 , such that T(n)
<= cn , Ɏ n >= n0 .
Proof: Suppose the claim is true for all values <= n/2
then
T(n)=2T(n/2)+1 (given)
<= 2.c.(n/2) +1 (by induction
hypothesis)
= cn+1
<= (c+1) n , Ɏ n>=1
Why is it Wrong?
Note that T(n/2)<=cn/2 => T(n)<=(c+1)n (this
statement is true but does not help us in
establishing a solution to the problem)

T(1)<=c (when n=1)


T(2)<=(c+1).2
T(2^2)<=(c+2).2^2 .
.
.
.
T(2^i)<=(c+i).2^I
So, T(n)= T(2^logn)= (c+ log n)n
= Ɵ (n log n)
What if we have extra lower order
terms?
• So, does that mean that the claim we initially
made that T(n)=O(n) was wrong ?
• No.
• Recall:
• T(n)=2T(n/2)+1 (given)
<= 2.c.(n/2) +1 (by induction hypothesis)
= cn+1
• Note that in the proof we have an extra lower
order term in our inductive proof.
Given Recurrence: T(n) = 2T(n/2) + 1
Guess: T(n) = O(n)
Claim : Ǝ some constant c and n0 , such that T(n) <= cn - b , Ɏ n >= n0
Proof: Suppose the claim is true for all values <= n/2
then
T(n)=2T(n/2)+1
<=2[c(n/2)-b]+1
<= cn-2b+1
<= cn-b+(1-b)
<= cn-b , Ɏ b>=1

Thus, T(n/2) <= cn/2 – b


=> T(n) <= cn – b, Ɏ b>=1

Hence, by induction T(n) = O(n), i.e. Our claim was true.

Hence proved.
Solving Recurrences using Recursion Tree Method

• Here while solving recurrences, we divide the problem into


subproblems of equal size.

For e.g., T(n) = a T(n/b) + f(n) where a > 1 ,b > 1 and f(n) is a given
function .

F(n) is the cost of splitting or combining the sub problems.

T n/b T n/b

Thanks : MCA 2012 Anurag


Aggarwal and Aniruddh Jarial
1) T(n) = 2T(n/2) + n

The recursion tree for this recurrence is :

n
n
T n/2 T n/2
n/2 n/2 n

log2 n n/22 n/22 n/22 n/22


:
:
:

1 1 1 1 1 1 1

Thanks : MCA 2012 Anurag


Aggarwal and Aniruddh Jarial
When we add the values across the levels of the recursion tree, we get a
value of n for every level.

We have n + n + n + …… log n times


= n (1 + 1 + 1 + …… log n times)
= n (log2 n)
= Ɵ (n log n)

T(n) = Ɵ (n log n)

Thanks : MCA 2012 Anurag


Aggarwal and Aniruddh Jarial
II.
Given : T(n) = 2T(n/2) + 1
Solution : The recursion tree for the above recurrence is

1 1 2

log n 4

:
:
:

Thanks : MCA 2012 Anurag


Aggarwal and Aniruddh Jarial
Now we add up the costs over all levels of the recursion tree, to determine
the cost for the entire tree :

We get series like


1 + 2 + 22 + 23 + …… log n times which is a G.P.

[ So, using the formula for sum of terms in a G.P. :


a + ar + ar2 + ar3 + …… + ar n – 1 = a( r n – 1 )
r – 1 ]
= 1 (2log n – 1)
2–1
= n–1
= Ɵ (n – 1) (neglecting the lower order terms)
= Ɵ (n)

Thanks : MCA 2012 Anurag


Aggarwal and Aniruddh Jarial
III.
Given : T(n) = T(n/3) + T(2n/3) + n
Solution : The recursion tree for the above recurrence is

n
n
n/3 2n/3
n/3 2n/3 n
n 2 n 1 2n n .
log3 n (3/2)2
log3/2 n
32 3 3 3 3
n
1 n/3i
:
:
:

Thanks : MCA 2012 Anurag


Aggarwal and Aniruddh Jarial
When we add the values across the levels of the recursion tree , we get a
value of n for every level.

Since the shortest path from the root to the leaf is


n → n → n → n → …. 1
3 32 33

we have 1 when n = 1
3i
=> n = 3i
Taking log₃ on both the sides
=> log₃ n = i

Thus the height of the shorter tree is log₃ n


T(n) > n log₃ n … A

Thanks : MCA 2012 Anurag


Aggarwal and Aniruddh Jarial
Similarly, the longest path from root to the leaf is
n → 2 n → 2 2n → …1
3 3

So rightmost will be the longest


when 2 k n =1
3

or n = 1
(3/2)k

=> k = log3/2 n

T(n) < n log3/2 n … B

Since base does not matter in asymptotic notation , we guess


from A and B
T(n) = Ɵ (n log2 n)
Thanks : MCA 2012 Anurag
Aggarwal and Aniruddh Jarial
Solving Recurrences
• Another option is “iteration method”
– Expand the recurrence
– Work some algebra to express as a
summation
– Evaluate the summation
• We will show some examples
Assignment 4
• Solve the following recurrence:

T(n) = T(αn) + T(βn) + n,


where 0 < α ≤ β < 1

Assume suitable initial conditions.


The Master Theorem
• Given: a divide and conquer algorithm
– An algorithm that divides the problem of size
n into a subproblems, each of size n/b
– Let the cost of each stage (i.e., the work to
divide the problem + combine solved
subproblems) be described by the function
f(n)
• Then, the Master Theorem gives us a
cookbook for the algorithm’s running time:
The Master Theorem
• if T(n) = aT(n/b) + f(n) then
 

  
n 
logb a
 
f (n)  O n logb a  

 
   0
T (n)   n  logb a
log n  
f ( n)   n 
logb a

  c 1
 
 f (n)   
f (n)   n logb a  AND 
 
 af (n / b)  cf (n) for large n
Using The Master Method
• T(n) = 9T(n/3) + n
– a=9, b=3, f(n) = n
– nlog a = nlog 9 = (n2)
b 3

– Since f(n) = O(nlog 9 - ), where =1, case 1


3

applies:


T ( n)   n logb a
 when f (n)  O n log b a 

– Thus the solution is T(n) = (n2)
More Examples of Master’s
Theorem
• T(n) = 3T(n/5) + n
• T(n) = 2T(n/2) + n
• T(n) = 2T(n/2) + 1
• T(n) = T(n/2) + n
• T(n) = T(n/2) + 1
When Master’s Theorem cannot
be applied
• T(n) = 2T(n/2) + n logn
• T(n) = 2T(n/2) + n/ logn
Up Next

Proving the correctness of Algorithms

You might also like