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$ Commented Nov 25, 2022 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
    Commented Nov 25, 2022 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$ Commented Nov 25, 2022 at 23:07
  • $\begingroup$ @RohitPandey: the significant ? $\endgroup$
    – user16034
    Commented Nov 27, 2022 at 15:40
  • $\begingroup$ Sorry, meant significance. Wanted to see if you can elaborate on it and why its important. $\endgroup$ Commented Nov 27, 2022 at 22:15
  • $\begingroup$ @RohitPandey: er, the significance is that it imposes the parity. $\endgroup$
    – user16034
    Commented Nov 28, 2022 at 8:45
  • $\begingroup$ So in merge sort, there are leftovers? $\endgroup$ Commented Nov 28, 2022 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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