Design and Analysis of Algorithms

234 Design and Analysis of Algorithms

9.1 Consider all the algorithms you have studied

till now and identify those which can be said

to be using D&C strategy.

9.2 Can we make a general statement that “if a

problem can be split using D&C strategy in

almost equal portions at each stage, then it

is a good candidate for recursive implemen-

tation, but if it cannot be easily divided into

equal portions, then it is better to be imple-

mented iteratively”? Explain with the help of

an example.

9.3 It is suggested that mergesort is not a good

strategy for arrays of size less than about 8 to

16, for which “insertion sort” may be better.

Realising that ...