2
$\begingroup$

Why does the Cooley-Tukey Fast Algorithm take $O(n \log n)$ time? The book derives this from the fact that evaluation takes time:

$T(n) = 2T(n/2) + O(n)$

and then uses the Master Theorem to arrive at the Big O Notation Time. Could someone explain how the above equation was derived?

How I see it:

After a recursion, you are dealing with twice the number of polynomials ($A_o(x)$ AND $Ae(x)$) at half the number of points, (since the points are plus-minutes pairs) and each polynomial is of half the size. So why isn't the time:

$T(n/2)+O(n)$

The size of the problem reduces by half (since the degree of $Ao(x)$ and $Ae(x)$ are half of $A(x)$) but your dealing with the same number of problems. ($A_o(x)$ and $A_e(x)$ at half the number of points.) What am I misunderstanding? 

Example

Lets say you are evaluating polynomial $A(x)$ at points: $a, -a, b, -b.$ Therefore you have 4 polynomials to evaluate: $A(a), A(-a), A(b), A(-b).$

Using the algorithm, you would instead evaluate the odd and even coefficient polynomials. Therefore you would evaluate:

1) $A_e(a^2)$

2) $A_o(a^2)$

3) $A_e(-a^2)$

4) $A_o(-a^2)$

5) $A_e(b^2)$

6) $A_o(b^2)$

7) $A_e(-b^2)$

8) $A_o(-b^2)$

Each polynomial is half the size of the original polynomial. However $A_e(a^2)$ and $A_o(a^2) = A_e(-a^2)$ and $A_e(-a^2)$. The same thing applies for $b$ and $-b$. Therefore you would actually only need to evaluate 4 polynomials:

1) $A_e(a^2)$

2) $A_o(a^2)$

5) $A_e(b^2)$

6) $A_o(b^2)$

Therefore you end up with the same amount of problems, but each problem is half the size, since $A_o$ and $A_e$ have half the degree of $A(x)$. Therefore 4 problems of size $n$ has been transformed into 4 problems of size $n/2$! The number of problems have stayed the same, only the size has changed, leading me to the conclusion that the time is:

$T(n) = T(n/2)+O(n)$

2 Answers 2

1

Using this pseudocode, you can see that lines 5-6 recurse on two roughly equal-sized arrays, hence the first term. The loop in lines 7-11 executes $N/2 = \Theta (n) $ times, explaining the second term. Assuming the rest of the code is negligible work, you're done.

Your example is perfectly valid, but the algorithm does not know that it only needs to evaluate four polynomials. Rather, it continues to recurse until it has reached $N$ problem instances of size $1$ and then iteratively pieces them together.

  • 0
    @TimDuff It does, thanks!2012-06-15
1

In all divide-and-conquer algorithms you see this general approach. Let's review: suppose you have a problem of size $n$.

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 

Now let's split the problem in half and recurse on each half:

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX          /                 \ XXXXXXXXXXXXXXXXXX   XXXXXXXXXXXXXXXXX 

Suppose we used $O(n)$ time to perform the split and $O(n)$ time to reassemble the returned values from the recursion. Then the running time is described by

$T(n) = 2T(n/2) + O(n).$

This, in fact, is the running time for mergesort, for example. Then by the master theorem, we get $T(n) = O(n\lg n)$.

Ok, so your issue is that you think that the recurrence for $T(n)$ is wrong: the problem is half as big (because we cut it in half) but there is only one subproblem because after all it's just the original problem rearranged into halves, right? But this is incorrect. There are two subproblems of size $n/2$ as you see from the picture above. If you think of a single sub-problem the picture would be:

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX          /                  XXXXXXXXXXXXXXXXXX 

where you recurse only on one half. This is, in fact, the running time for binary search, and its running time is $T(n) = T(n/2) + O(1) = O(\lg n).$

In general, if we have $T(n) = aT(n/b) + O(n^d)$ to represent the running time of a divide and conquer algorithm, the $a$ indicates the number of recursive calls made at a given level of recursion. Our $a$ is 2 because we recurse on two sub-problems of size (meaning degree and number of coefficients) $n/2$.