Design and Analysis of Algorithms: Divide and Conquer Methodology

Design and Analysis of Algorithms
Session 4
Divide and Conquer Methodology
Divide and Conquer Technique
General Method:
 The Divide and Conquer Technique splits n inputs into k subsets ,

1< k ≤ n, yielding k sub problems.
 These sub problems will be solved and then combined by using a

separate method to get a solution to a whole problem.
 If the sub problems are large, then the Divide and Conquer Technique
will be reapplied.
 Often sub problems resulting from a Divide and Conquer Technique

are of the same type as the original problem.
Divide-and-Conquer
• Divide the problem into a number of sub-problems
– Similar sub-problems of smaller size
• Conquer the sub-problems

– Solve the sub-problems recursively
– Sub-problem size small enough  solve the problems in

straightforward manner
• Combine the solutions of the sub-problems

– Obtain the solution for the original problem
General method for Divide and Conquer Technique
Algorithm DAndC(p)
{
if Small(p) then return s(p);
else
{
divide p into smaller instances p1,p2,…….,pk, k≥1;
Apply DAndC to each of these subproblems;
return Combine(DAndC(p1), DAndC(p2),…, DAndC(pk));
}
}
If the size of p is n and the sizes of the k sub problems are n 1,n2,….,nk, then
the computing time of DAndC is described by the recurrence relation
T(n)= g( n) n small
T(n1)+T(n2)+……+T(nk)+f(n) Otherwise
 Where T(n) is the time for DAndC on any input of size n and g(n) is the
time to compute the answer directly for small inputs.
 The function f(n) is the time for dividing p and combining the solutions to
sub problems.
There are 2 methods for solving an recurrence relation
• Substitution method
• Master’s theorem
Substitution method
Example: Consider the case in which a=2 and b=2. Let T(1)=2
and f(n)=n. We have
T(n) = 2T(n/2)+n
= 2[2T(n/4)+n/2]+n
= 4T(n/4)+2n
=4[2T(n/8)+n/4]+2n
= 8T(n/8)+3n
:
=2iT(n/2i)+in, for any log2n>=i>=1
=2log2nT(n/2log2n)+nlog2n
Thus, T(n)=nT(1)+nlog2n=nlog2n+2n
Master’s Theorem
• Master Method is a direct way to get the solution. The
master method works only for following type of
recurrences or for recurrences that can be transformed to
following type.
• T(n) = aT(n/b) + f(n) where a >= 1 and b > 1, f(n) is a
positive function
• There are following three cases:
1. If f(n) = Θ(nc) where c < Logba then T(n) = Θ(nLogba)
2. If f(n) = Θ(nc) where c = Logba then T(n) = Θ(ncLog n)
3.If f(n) = Θ(nc) where c > Logba then T(n) = Θ(f(n))
Examples
Problem-01:
Solve the following recurrence relation using Master’s
theorem- T(n) = 3T(n/2) + n2
Solution-
We compare the given recurrence relation with
T(n) = aT(n/b) + θ (nclogpn).
Then, we have- a = 3,b = 2,c = 2,p = 0
Now, a = 3 and bc = 22 = 4.
Clearly, a < bc.
So, we follow case-03.
Since p = 0, so we have- T(n) = θ (nclogpn)
T(n) = θ (n2log0n)
Thus, T(n) = θ (n2)
Problem-02:
theorem- T(n) = 2T(n/2) + nlogn
Solution-

Then, we have- a = 2, b = 2, k = 1, p = 1

Now, a = 2 and bc = 21 = 2.
Clearly, a = bc. So, we follow case-02.

Since p = 1, so we have- T(n) = θ (nlogba.logp+1n)
T(n) = θ (nlog22.log1+1n)
Thus, T(n) = θ (nlog2n)
Problem-03:
theorem- T(n) = 2T(n/4) + n0.51
Solution-
Then, we have- a = 2, b = 4, c = 0.51, p = 0

Now, a = 2 and bc = 40.51 = 2.0279.
Clearly, a < bc.
Since p = 0, so we have- T(n) = θ (nclogpn)
T(n) = θ (n0.51log0n)
Thus, T(n) = θ (n ) )
T(n) = θ (n0.51
0.51
Problem-04:
theorem- T(n) = √2T(n/2) + logn
Solution-
T(n) = aT(n/b) + θ (nklogpn).
Then, we have- a = √2, b = 2, c = 0, p = 1
Now, a = √2 = 1.414 and bc = 20 = 1.
Clearly, a > bc.
So, we have- T(n) = θ (nlogba) T(n) = θ (nlog2√2)
Problem-05:

theorem-
T(n) = 8T(n/4) – n2logn

Solution-

•The given recurrence relation does not correspond to the
general form of Master’s theorem.
•So, it can not be solved using Master’s theorem.
Problem-06:
theorem- T(n) = 3T(n/3) + n/2
Solution-
We write the given recurrence relation as T(n) = 3T(n/3) + n.
Now, we can easily apply Master’s theorem.
We compare the given recurrence relation with T(n) = aT(n/b)
+ θ (nclogpn).
Then, we have- a = 3, b = 3, c = 1, p = 0
Now, a = 3 and bc = 31 = 3.
Clearly, a = bc.So, we follow case-02.
Since p = 0, so we have- T(n) = θ (nlogba.logp+1n)
T(n) = θ (nlog33.log0+1n) T(n) = θ (n1.log1n)
Problem-07:
Form a recurrence relation for the following code and
solve it using Master’s theorem-
A(n)
{
if(n<=1) return 1;
else return A(√n);
}
Solution-
•We write a recurrence relation for the given code as T(n) = T(√n) + 1.
•Here 1 = Constant time taken for comparing and returning the value.
•We can not directly apply Master’s Theorem on this recurrence relation.
•This is because it does not correspond to the general form of Master’s
theorem.
•However, we can modify and bring it in the general form to apply
Master’s theorem.
Let- n = 2m ……(1)
Then- T(2m) = T(2m/2) + 1

Now, let T(2m) = S(m), then T(2m/2) = S(m/2)

So, we have- S(m) = S(m/2) +1
Now, we can easily apply Master’s Theorem.

We compare the given recurrence relation with S(m) = aS(m/b) + θ (mclogpm).
Then, we have- a = 1, b = 2, c = 0, p = 0
Now, a = 1 and bc = 20 = 1.
Clearly, a = bc. So, we follow case-02.
Since p = 0, so we have- S(m) = θ (mlogba.logp+1m)
S(m) = θ (mlog21.log0+1m) = θ (m0.log1m)

Thus, S(m) = θ(logm) ……(2) Now, From (1), we have n = 2m.
So, logn = mlog2 which implies m = log2n.
Substituting in (2), we get- S(m) = θ(loglog2n) OrT(n) = θ (loglog2n)
Master Theorem Limitations
The master theorem cannot be used if:
• T(n) is not monotone. eg. T(n) = sin n
• f(n) is not a polynomial. eg. f(n) = 2n
• a is not a constant. eg. a = 2n
• a<1

Design and Analysis of Algorithms: Divide and Conquer Methodology

Uploaded by

Copyright:

Available Formats

Design and Analysis of Algorithms: Divide and Conquer Methodology

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Design and Analysis of Algorithms: Divide and Conquer Methodology

Uploaded by

Copyright:

Available Formats

Design and Analysis of Algorithms

 The Divide and Conquer Technique splits n inputs into k subsets ,

 These sub problems will be solved and then combined by using a

 Often sub problems resulting from a Divide and Conquer Technique

• Conquer the sub-problems

– Sub-problem size small enough  solve the problems in

• Combine the solutions of the sub-problems

The master theorem cannot be used if:

• T(n) is not monotone. eg. T(n) = sin n

• f(n) is not a polynomial. eg. f(n) = 2n

• a is not a constant. eg. a = 2n

You might also like