Discrete Mathematics

-------------------------'DESIGN

OF

ALGORITHMS

313

11.4.1

Model

of

Divide

and

Conquer

The model is given in terms

of

a sequence so that split returns a point in the sequence for dividing the

sequence among the two sub-problems. However, divide and conquer is not restricted to sequence problems.

do(x:y) {

split(x:y)

->

splitpoint

part]

= do(x:splitpoint)

part2 = do( splitpoint:y)

return combine(

part]

,part2)

}

If

the combine/split processing is expensive, this approach fails to show any advantage.

Obviously, simply splitting a problem and solving the parts cannot improve performance. So what is

the advantage

of

this approach? There are two ...