Background: The Fast Fourier Transform (FFT) takes n complex numbers as input and produces n complex numbers as output. (Dont Panic! You don't need to know anything more about FFT's for this problem.) We will only consider FFT's when n is a power of two, i.e. n = 2^k. One way to compute the Fast Fourier on n elements is by the so-called "four step method", which is really divide and conquer.

• Step 1: Write the elements into a rectangular array in row major order. If n is a perfect square, the array should be square, i.e. with 2^(k/2) rows and 2^(k/2) columns. [Otherwise, we could make the array twice as wide as it is high, but we won't be concerned with this in this problem.] For each column of this matrix, take the FFT of the elements in the column (this is done recursively, of course). The recursion stops when you end up with just two elements, which takes 10 floating point operations.
• Step 2: Multiply each element of the array by an appropriately-chosen constant (these constants are called, and I am not making this up, the "twiddle factors"). Since we are dealing with complex numbers, this takes 6 floating point operations per element.
• Step 3: Transpose the matrix. In the standard analysis of FFT's, this is considered to be "free" since it doesn't involve any floating-point operations.
• Step 4: Take the FFT (recursively) of each column.

For simplicity, let's just consider the case that n is of the form 2^(2^j), since then we'll always get perfect squares at each level of recursion.

Finally, we get to the questions:

(a) Write the recursive formula for T(n), the complexity of the four-step method of computing FFT's in terms of floating-point operations. [Don't solve it yet - that's part (c).]

(b) Consider a different divide and conquer problem that results in the related but easier (I think) recursion:
S(n) = n^.5 x S(n^.5) + n
S(2) = 1
Find the asymptotic complexity (in big-Theta notation) of S(n). You can restrict yourself to the case that n is of the form 2^(2^j), so that whenever you take the square root, you get an integer.

(c) [Warning: this may be hard. At least, I don't immediately see how to solve it, even though I think I know the answer.]

Find the asymptotic complexity (in big-Theta notation) for the Four Step method of doing FFT's. You can just consider the case that n = 2^(2^j).

Incidentally, for a different method of computing the FFT of n numbers (with n a power of 2), the complexity is 10 n lg n. If you like the "substitution method", you might try this as a first guess.

(a) Describe some plausible (or even implausible) situation where having a good algorithm for a certain problem would help save money or resources or make the world a better place or whatever. Try not to make it too complicated, but not trivial either. [A random example of what I'm looking for is the "space shuttle experiment problem", as described in first full paragraph on page 693 of the textbook.]

(b) Give a consise mathematical formulation of your problem.

Please note that I am not asking you to devise an algorithm for your problem (... yet).