Algorithm

Divide and Conquer Algorithms
and
Recurrence Relations
Debdeep Mukhopadhyay
IIT Madras
Divide & Conquer Algorithms
• Many types of problems are solvable by

reducing a problem of size n into some
number a of independent subproblems,
each of size ≤⎡n/b⎤, where a≥1 and b>1.
• The time complexity to solve such
problems is given by a recurrence
relation: Time to combine the
solutions of the
– T(n) = a·T(⎡n/b⎤) + g(n) subproblems into a
Time for each subproblem solution
of the original problem.
Why the name?
• Divide: This step divides the problem into
one or more substances of the same
problem of smaller size
• Conquer: Provides solutions to the bigger
problem by using the solutions of the
smaller problem by some additional work.
Divide and Conquer Examples
• Binary search: Break list into 1 sub-
problem (smaller list) (so a=1) of size
≤⎡n/2⎤ (so b=2).
– So T(n) = T(⎡n/2⎤)+ 2 (g(n)=c constant)
– g(n)=2, because two comparisons are needed
to conquer. One to decide which half of the
list to use. Second to decide whether any
term in the list remain.
Find the maximum and minimum of
a sequence
• If n=1, the number is itself min or max
• If n>1, divide the numbers into two lists.
Decide the min & max in the first list. Then
choose the min & max in the second list.
• Decide the min & max of the entire list.
• Thus,
T(n)=2T(n/2)+2
Fast Multiplication Example
• The ordinary grade-school algorithm takes
Θ(n2) steps to multiply two n-digit numbers.
– Can we do better?
• Let’s find an asymptotically faster algorithm!
• To find the product cd of two 2n-digit base-b
numbers, c=(c2n-1c2n-2…c0)b and
d=(d2n-1d2n-2…d0)b, first, we break c and d in
half:
c=bnC1+C0, d=bnD1+D0
Derivation of Fast Multiplication
cd = (b nC1 + C0 )(b n D1 + D0 )
(Multiply out
= b C1 D1 + b (C1 D0 + C0 D1 ) + C0 D0 polynomials)
2n n
= b 2 nC1 D1 + C0 D0 + Zero
b n (C1 D0 + C0 D1 + (C1 D1 − C1 D1 ) + (C0 D0 − C0 D0 ))

= (b 2 n + b n )C1 D1 + (b n + 1)C0 D0 +
b n (C1 D0 − C1 D1 − C0 D0 + C0 D1 )
= (b 2 n + b n )C1 D1 + (b n + 1)C0 D0 +
b n (C1 − C0 )( D0 − D1 ) (Factor last term)
Three multiplications, each with n-digit numbers
Recurrence Rel. for Fast Mult.
Notice that the time complexity T(n) of the
fast multiplication algorithm obeys the
recurrence:
• T(2n)=3T(n)+Θ(n) Time to do the needed adds &
subtracts of n-digit and 2n-digit
i.e., numbers
• T(n)=3T(n/2)+Θ(n)
So a=3, b=2.
Solving the R.R
• We have seen some approaches before.
• We shall discuss some more useful
techniques
• Let, n=bk, k is a positive integer
– f(n)=af(n/b)+g(n)
=a2f(n/b2)+ag(n/b)+g(n)
=a3f(n/b3)+a2g(n/b2)+ag(n/b)+g(n)
… =akf(n/bk)+Σk-1
0
a jg(n/bj).
If n=bk, we have f(1) in place of n/bk.

Theorem
• Let f be a non-decreasing function satisfying:
f(n)=af(n/b)+c, where n is divisible by b, a≥1, b
is an integer greater than 1, and c is a positive
real number.
• Then
⎧ O(n logb a ), a > 1
f ( n) = ⎨
⎩O (log b n), a = 1
Theorem contd.
• When n=bk, we have further:
f (n) = C1n logb a + C2 ,
where C1 = f (1) + c /(a − 1), C2 = −c /(a − 1)
Examples
• f(n)=5f(n/2)+3, f(1)=7. Find f(2k), k is a positive
integer
• f(n)=5kf(1)+3(1+5+52+…+5k-1)
=5kf(1)+3(5k-1)/4 [GP series]
=5k[f(1)+3/4]-3/4
Since, f(n) is a non-decreasing function,
f(n) is O(n log2 5 ).
Examples
• Estimate the number of searches in Binary
Search
Solve: f(n)=f(n/2)+2
a=1=>f(n)=O(log2n)
• Estimate the number of comparsons to find
the min-max of a sequence (using the algo
previously stated)
Solve: f(n)=2f(n/2)+2
f(n)= O(nlog 2 ) = O(n)
2
The Master Theorem
Consider a function f(n) that, for all n=bk
for all k∈Z+,,satisfies the recurrence
relation:
f(n) = af(n/b) + cnd
with a≥1, integer b>1, real c>0, d≥0.
Then:
⎧O(n d ) if a < b d
⎪
f (n) ∈ ⎨O(n d log n) if a = b d
⎪O(nlogb a ) if a > b d
⎩
Master Theorem Example
• Recall that complexity of fast multiply was:
T(n) = 3T(n/2) + Θ(n)
• Thus, a=3, b=2, d=1. So a > bd, so case 3
of the master theorem applies, so:
T (n) = O(n logb a
) = O(n log2 3
)
which is O(n1.58…), so the new algorithm is

strictly faster than ordinary Θ(n2) multiply!

Algorithm

Uploaded by

Copyright:

Available Formats

Algorithm

Uploaded by

Document Information

Original Description:

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

Algorithm

Uploaded by

Copyright:

Available Formats

Divide and Conquer Algorithms

• Many types of problems are solvable by

b n (C1 D0 + C0 D1 + (C1 D1 − C1 D1 ) + (C0 D0 − C0 D0 ))

If n=bk, we have f(1) in place of n/bk.

which is O(n1.58…), so the new algorithm is

You might also like