§ FFT

• Evaluating a polynomial p(x) at [a0, a1, ... am] in general is hard, even though we have the recurrence p(x) = po(x^2) + x pe(x^2). This makes the polynomials smaller (degree of po, pe is half of that of p). However, we need to evaluate at all the points [a0...am] , so to merge we need to merge values at [a0...am] at each step. So our recurrence will be T(n) = T(n/2) + m with T(1) = m. This solves to O(nm).
• The special property of DFT is that we can reconstruct p(x) at [w[n][0], ... wn[n][n-1]] given the values of po, pe at [w[n/2][1], w[n/2][2], w[n/2][3], ... w[n/2][n/2-1]]. So the number of points we need to evaluate the polynomial decreases with the size of the polynomial!
• This makes the recurrence T(n) = T(n/2) + n with T(1) = 1 which is O(n log n).

§ Worked out example of FFT of 8 elements

Now suppose we know how to evaluate $p_e(x)$ and $p_o(x)$ at $[w_4^0, w_4^1, w_4^2, w_4^3]$. where $w_4$ is the 4th root of unity. We wish to evaluate $p(x)$ at $[w_8^0, w_8^1, w_8^2, \dots, w_8^7]$, where $w_8$ is the 8th root of unity. The only two properties of the roots of unity we will need are:

• $w_8^2 = w_4$.
• $w_8^4 = -1$.

Using the value of $w_8$, the above two relations, the values $p_o(w_4^k) = [p_o(1), p_o(w_4, p_o(w_4^2), p_o(w_4^3)]$ and $p_e(w_4^k) = [p_e(1), p_e(w_4), p_e(w_4^2), p_e(w_4^3)]$, we evaluate $p$ at powers of $w_8$ ( $[p(w_8^k)]$ ) as:

• $p(w_8^k) = p_e((w_8^k)^2) + w_8^k p_o((w_8^k)^2) = p_e(w_4^k) + w_8^k p_o(w_4^k)$.
• $p(w_8^0) = p_e((w_8^0) + w_8^0 p_o(w_8^0) = p_e(1) + p_o(1)$
• $p(w_8^1) = p_e(w_8^2) + w_8^1 p_o(w_8^2) = p_e(w_4^1) + w_8 p_o(w_4^1)$
• $p(w_8^2) = p_e(w_8^4) + w_8^2 p_o(w_8^4) = p_e(w_4^2) + w_8^2 p_o(w_4^2)$
• $p(w_8^3) = p_e(w_8^6) + w_8^3 p_o(w_8^6) = p_e(w_4^3) + w_8^3 p_o(w_4^3)$
• $p(w_8^4) = p_e(w_8^8) + w_8^4 p_o(w_8^8) = p_e(w_4^4) + w_8^4 p_o(w_4^4) = p_e(1) - p_o(1)$

§ Solving the Recurrence: T(n) = n + T(n/2), with T(1) = 1

§ Proof 1:

Expand the recurrence:

= T(n)
= n + 2T(n/2)
= n + 2[n/2 + T(n/4)]
= n + n + 4T(n/4)
= n + n + 4[n/4 + 2T(n/8)]
= n + n + n + 8T(n/8)
= ...
= kn + ... 2^k T(n/2^k)
= (log n)n + 2^(log n) T(n/2^(log n))
= (log n)n + n T(n/n)
= (log n)n + n* 1
= (log n)n + n

§ Proof 2:

Consider the tree:

           8
          mrg:8
   4                 4
   mrg:4           mrg:4
  2     2          2       2
 mrg:2  mrg:2     mrg:2   mrg:2
 1 1    1  1      1   1    1  1

• Number of leaves is n. Cost of each leaf is T(1) = 1. Total cost of leaf level is n.
• At each level above, total cost is 8 = 4*2 = 2*4.
• Number of levels in log n.
• Total cost is cost of leaf n, plus cost of interior nodes n log n.