A Universe of Sorts

§ 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

p(x) \equiv a_0 x^0 + a_1 x^1 + a_2 x^2 + a_3 x^3 + a_4 x^4 + a_5 x^5 + a_6 x^6 + a_7 x^7 p_e(x) \equiv a_0 x^0 + a_2 x + a_4 x^2 + a_6 x^3 \\ p_o(x) \equiv a_1 + a_3 x + a_5 x^2 + a_7 x^3 \\ P(x) = p_e(x) = x p_o(x)

Now suppose we know how to evaluate

p_e(x)

and

p_o(x)

[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)

[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.

§ FFT

§ Worked out example of FFT of 8 elements

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

§ Proof 1:

§ Proof 2:

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