Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
That ought to be a capital theta, $N/2 = \Theta(n)$. –  Rahul Jun 14 '12 at 0:01
    
But after the recursion, you are dealing with twice the number of polynomials ($A_o(x)$ AND $A_e(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 $A_o(x)$ and $A_e(x)$ is 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? –  user26649 Jun 14 '12 at 0:43
    
@Riddler: As you say, you split the $n$ size problem into two $n/2$ size problems. The coefficient $2$ on $T(n/2)$ reflects this. It says you have two problems of half the size. The $n/2$ reflects the fact that the problems are half the size. Then the $O(n)$ reflects the effort to combine the two (half) solutions into one. –  Ross Millikan Jun 14 '12 at 2:33
1  
@Riddler: You have identified the problem precisely. The fact that $A_e$ and $A_o$ have half the coefficients is captured in the $n/2$ of T(n/2)$. But the claim that $A_e(a^2)=A_e(-a^2) is not correct unless there is symmetry in the data. This is what Fixee was getting at in his/her response. –  Ross Millikan Jun 14 '12 at 3:20
1  
@Riddler - I hope my most recent edit clarifies the problem. –  Tim Duff Jun 15 '12 at 19:11
show 4 more comments

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.