0
$\begingroup$

Merge sort and FFT are both divide and conquer algorithms that split the input in two repeatedly. While merge sort can be applied to any $n$, the FFT algorithm given in CLRS (section 30.2, third edition) only applies when $n$ is a power of $2$. How come we can forge ahead with any $n$ for merge sort, but not quite for FFT?

$\endgroup$
2
  • $\begingroup$ I think the recursive step works fine, but the problem is the halving lemma (lemma 30.5) $\endgroup$ Nov 25 at 1:07
  • 1
    $\begingroup$ Hi @Rohit, I think you're right, at least for $n$ odd. The first edition even says about the Halving lemma, "if $n>0$ is even,...". Again, for $n$ odd, when you take powers greater than $n/2$, you run into problems, since $\left( \omega_{n/2} \right)^{n/2 +1}$ presents problems if you consider the Cancellation lemma. You would be essentially trying to get an odd power from an even power, or vice versa. $\endgroup$
    – Matt Groff
    Nov 25 at 4:14

1 Answer 1

1
$\begingroup$

Short answer:

A merge works with individual elements. Any numbers can be handled. In particular, natural mergesort does merge sequences of arbitrary lengths.

The FFT works on pairs of elements, with no leftovers. So there must be an even number of them, and by recurrence, a power of $2$.


Variants of the FFT can be based on other primes, and can be combined to work for composite $n$, but they don't reach the efficiency of binary FFT.

$\endgroup$
5
  • $\begingroup$ What is the significant of "no leftovers"? $\endgroup$ Nov 25 at 23:07
  • $\begingroup$ @RohitPandey: the significant ? $\endgroup$ Nov 27 at 15:40
  • $\begingroup$ Sorry, meant significance. Wanted to see if you can elaborate on it and why its important. $\endgroup$ 2 days ago
  • $\begingroup$ @RohitPandey: er, the significance is that it imposes the parity. $\endgroup$ 2 days ago
  • $\begingroup$ So in merge sort, there are leftovers? $\endgroup$ 2 days ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.