Algorithms and Data Structures for Programming Contests

Divide-and-Conquer Algorithms (Cont'd)

Regroup

Runtime satisfies recurrence T(n) = 4 T(n/2) + O(n).
So by Master Theorem, T(n) = O(n²) — no better than iterative algorithm!

Key insight

• Consider product (X1 + X0) (Y1 + Y0). This computes p1 + p2 + p3 + p4 (using variables from the program above) with only one recursive multiplication.

Resulting algorithm and runtime

• Algorithm:

      multiply(X, Y):
          if n == 1:
              return x * y  # multiplication of 1-bit integers
          else:
              set lists X1, X0, Y1, Y0 as above
              p1 = multiply(X1, Y1)
              p2 = multiply(X0+X1, Y0+Y1)
              p3 = multiply(X0, Y0)
              return 2**n * p1 + 2**(n/2) * (p2 - p1 - p3) + p3
  

• Runtime?
  Satisfies recurrence T(n) = 3 T(n/2) + O(n).
  So by Master Theorem, T(n) = O(n^log₂ 3).
• This is much better than the previous algorithm, because log₂ 3 = 1.58...

How did this happen?

• Saving one recursive call propagates through all of the sub-calls and results in substantial savings, as long as this does not increase the time taken outside recursive calls by more than a constant factor.

Moral

• Consider extra work to save recursive calls, when your recursive algorithms run too slowly.

More Examples

Mergesort

• Algorithm
• Runtime

Quicksort and Selection

• Algorithms
• Runtime
• Randomization

To learn more...

• Wikipedia entry on Divide-and-conquer algorithms.

Back to Algorithms

© Copyright 2012–2015 François Pitt <francois.pitt@utoronto.ca>
last updated at 08:24 (EST) on Thu 5 Mar 2015
Algorithms and Data Structures by François Pitt is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.