# Number of complex calculations in FFT and inverse FFT

1. Jan 26, 2015

### Jimmy Johnson

1. The problem statement, all variables and given/known data

Calculate the total number of compex multiplications required for the calculation in (b) when FFTs are used to perform the Discrete Fourier Transforms and Inverse Discrete Fourier Transforms.

There were two FFT multiplied together and one inverse FFT of that product to solve B.

x1(n) = [1, 0, −1, 1]

x2(n) = [2, 3, 2, 0, 1

2. Relevant equations

Nlog2N

3. The attempt at a solution

The vectors were padded with zeros but I'm working under the assumption that can be negated.

x1(n) = 4log24 = 8
x2(n) = 5log25 = 11.61

product of both created an 8 length vector

8log28 = 24

Do I add these? The 5 one doesn't seem correct, something about it being a prime factor that doesn't hold for the equation?

2. Jan 26, 2015

### Staff: Mentor

Note that the FFT algorithm scales as $O(N \log_2 N)$, not that the number of operations is exactly $N \log_2 N$ (I don't know if this is relevant to your problem, because I don't know how your teacher presented the material).

Why? What is the computer actually calculating?

You probably only learned about an algorithm that works for $2^N$ data points. Therefore an FFT on length 5 doesn't make any sense.

3. Jan 26, 2015

### Jimmy Johnson

What is the O on that scale equation?

The calculation is the circular convolution of the x1(t) and x2(t) through ifft(fftx1padded)*(fftx2padded), so the padding was adding zeroes to the vector so that it was the same length and therefore achievable in matlab? after convolution a length 8 was determined and x1&2(t) are 4&5 length vectors respectively?

So would my data points actually be 2^4 and 2^5?

4. Jan 26, 2015

### Staff: Mentor

It's big O notation. It tells you how an algorithm scales when you change the size of the data. If an algorithm is of order $O(n^2)$, then doubling the number of data points will result in about 4 times the number of operations. But it doesn't mean that it will perform exactly $n^2$ operations. The actual number of operations could be $4 n^2 + 2 n$.

Why is padding necessary? What do you think matlab is doing with these zeros?