# Optimal division sequences for divide-and-conquer algorithms

Say we have a discrete data set of some size, and we can use a recursive divide-and-conquer algorithm to process the data in some way (an FFT for example). The naive solution is, say, $n^2$ in complexity. At each recursion stage we have no, one, or many choices in how to divide the data, but it is important we divide the data in the right way as you can see in my example below: (I have used a data set of size 12 to illustrate)

1. 12 (complexity: $12^2 = 144$ [worst])
2. 12 $\rightarrow$ 1 (complexity: $12 \times 1^2 = 12$ [optimal])
3. 12 $\rightarrow$ 6 (complexity: $2 \times 6^2 = 72$)
4. 12 $\rightarrow$ 6 $\rightarrow$ 1 (complexity: $2 \times 6 = 12$ [optimal])
5. 12 $\rightarrow$ 6 $\rightarrow$ 3 (complexity: $2 \times 2 \times 3^2 = 36$)
6. 12 $\rightarrow$ 6 $\rightarrow$ 3 $\rightarrow$ 1 (complexity: $2 \times 2 \times 3 \times 1^2 = 12$ [optimal])
7. 12 $\rightarrow$ 6 $\rightarrow$ 2 (complexity: $2 \times 3 \times 2^2 = 24$)
8. 12 $\rightarrow$ 6 $\rightarrow$ 2 $\rightarrow$ 1 (complexity: $2 \times 3 \times 2 \times 1^2 = 12$ [optimal])
9. 12 $\rightarrow$ 4 (complexity: $3 \times 4^2 = 48$)
10. 12 $\rightarrow$ 4 $\rightarrow$ 1 (complexity: $3 \times 4 \times 1^2 = 12$ [optimal])
11. 12 $\rightarrow$ 4 $\rightarrow$ 2 (complexity: $3 \times 2 \times 2^2 = 24$)
12. 12 $\rightarrow$ 4 $\rightarrow$ 2 $\rightarrow$ 1 (complexity: $3 \times 2 \times 2 \times 1^2 = 12$ [optimal])
13. 12 $\rightarrow$ 3 (complexity: $4 \times 3^2 = 36$)
14. 12 $\rightarrow$ 3 $\rightarrow$ 1 (complexity: $4 \times 3 \times 1^2 = 12$ [optimal])
15. 12 $\rightarrow$ 2 (complexity: $6 \times 2^2 = 24$)
16. 12 $\rightarrow$ 2 $\rightarrow$ 1 (complexity: $6 \times 2 \times 1^2 = 12$ [optimal])

As you can see, for a very small number 12 we have at least 16 possible sequences.

Mathematically there are a number of optimals, however in practice not all optimals are the same as there is a small overhead for each level of recursion. From my experience with radix-2 FFT: when the data set gets to about 2, 4 or 8 (depending on the implementation), it's best to bail out of FFT and finish up with a DFT.

What is the best way to find the optimal division sequence for a data set of any given length? Ideally, the computation of this optimal sequence should not take so long that it is not worth doing in the first place.

-
Might be hard to tell. You know the example of quicksort performing very badly when given an input that's already sorted, right? –  Ｊ. Ｍ. Sep 12 '11 at 3:29
The way you have it set up, any scheme that gets down to 1 has the same, optimal, complexity of 12 (and I think you've left out $12\to6\to3\to1$ and $12\to3\to1$ and maybe some others). –  Gerry Myerson Sep 12 '11 at 3:48
@Gerry: Good observation. So I guess I need to do some experimental analysis on which of the down-to-one sequences performs the best in practice. –  Ozzah Sep 12 '11 at 4:05
Or you devise a way of choosing/guessing that will guarantee a good average case performance, as done for Quicksort. –  Raphael Sep 12 '11 at 6:41