0
$\begingroup$

$N:=2^p$

Input: $f \in \mathbb C^N$

1: $n=N/2$

2: initialize vectors $f^{(1)}, f^{(2)} \in \mathbb C^n$

3: $w_N^0=1$

4: for $j=0,\ldots,n-1$ do

5: $\ \ \ \ \ f_j^{(1)}=f_j+f_{j+n}$

6: $\ \ \ \ \ f_j^{(2)}=(f_j-f_{j+n})w_N^j$

7: $\ \ \ \ \ w_N^{j+1}=\exp(-2\pi i/N)w_N^j$

8: end for

9: if $N=2$ then

10: $\ \ \ \ \, $set $c:=(f^{(1)},f^{(2)})\in \mathbb C^2$

11: else

12: $\ \ \ \ \, $ evaluate (recursively) $c^{(1)}=FFT(f^{(1)})$

13: $\ \ \ \ \, $ evaluate (recursively) $c^{(2)}=FFT(f^{(2)})$

14: $\ \ \ \ \, $ set $c=\Big(c_0^{(1)},c_0^{(2)},c_1^{(1)},c_1^{(2)},\ldots,c_{n-1}^{(1)},c_{n-1}^{(2)}\Big) \in \mathbb C^n$

15: end if

Let $m_p$ be the number of multiplications and $a_p$ the number of additions for $N=2^p$. I want to show that

$$m_p\le p2^p, \ \ \ \ \ a_p\le p2^p, \ \ \ \ \ p\in \mathbb N$$

Therefore we have a total complexity of about $N \log (N)$ complex additions/ multiplications

We didn't hear about $\mathcal O$ yet, I first of all just want to understand why $a_p\le p 2^p$. I came across the following $f^{(1)},f^{(2)} \in \mathcal C^{2^{p-1}}$ so we have a 'recursion depth' of $p-1$, and $N$ additions and $N$ multiplications every time we run it. Therefore $a_p=2^p+2\times 2^{p-1}+4\times 2^{p-2}+\ldots + 2^{p-1}\times 2=p\times 2^p$. I don't know if this is correct and I don't get where $2^p+2\times 2^{p-1}+4\times 2^{p-2}+\ldots + 2^{p-1}\times 2$ comes from

$\endgroup$
  • 1
    $\begingroup$ You are asking for the time complexity of the well-known Fast Fourier Transform algorithm. The algorithm is well studied, so is its time complexity. And analysing the time complexity is easy peasy. (Proving that it does what it is supposed to do is tough, and finding bounds for the error is tough, but the time complexity is easy). So what have you done? What problems are you stuck on? $\endgroup$ – gnasher729 Nov 3 '19 at 8:35
  • $\begingroup$ @gnasher729 I editet my post $\endgroup$ – user711482 Nov 3 '19 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.