# Is it possible to reduce the complexity of radix-2 FFT if the input vector contains identical elements?

my question is about reducing the complexity of radix-2 FFT when the input vector has a specific structure.

For an input vector of x with N elements, the complexity is given by O(N log2 N).

My input vector y with N elements has the structure of: y = [x1 x2]T

where,

x1 = x2

and x1 and x2 vectors have N/2 elements. Is it possible to reduce the complexity of radix-2 FFT for this y vector? I think it is possible to not use one of the N/2 DFT blocks of the FFT algorithm in this case. Can anyone show me what is the complexity for this vector? Thanks in advance.

if

$$\text{FFT}\{[a, b, c, d]\} = [p, q, r, s]$$

then

$$\text{FFT}\{[a, b, c, d, a, b, c, d]\} = [p, 0, q, 0, r, 0, s, 0]$$

or $$=[2p, 0, 2q, 0, 2r, 0, 2s, 0]\text,$$

depending on normalization.

Edit: Using this property, we can make FFT nearly 2x faster on this specialized data. But the complexity is still $$O(n \log n)$$. I mean, big O notation doesn't count constant factor.

• Thank you. Assuming no normalization, i.e., DFT{x}=sum_{i=0}^{N-1} x_i e^{..}, it is known that FFT implementation leads to a complexity of N log_2 N. If we have a structured vector as above, i.e., x=[x_0,x_0,x_1,x_1,...,x_N/2,x_N/2], then can we say that the FFT complexity can be reduced to (N/2) log_2(N/2)? I appreciate your response in advance. – Mustafa Anıl Reşat Oct 22 '19 at 12:08
• @MustafaAnılReşat So what is actually your question? Something like [a, b, c, d, a, b, c, d] or [a, a, b, b, c, c, d, d] ? – mfcc64 Oct 23 '19 at 7:15
• Sorry for previous mistake. I should have written it as a vector structure of [a, b, c, d, a, b, c, d]. Let me repeat the question again correctly. Assuming no normalization, i.e., DFT{x}=sum_{i=0}^{N-1} x_i e^{..}, it is known that FFT implementation leads to a complexity of N log_2 N. If we have a structured vector as x=[x_0,x_1,...,x_N/2,x_0,x_1,...,x_N/2], then can we say that the FFT complexity can be reduced to (N/2) log_2(N/2)? I appreciate your response in advance. – Mustafa Anıl Reşat Oct 23 '19 at 11:20
• @MustafaAnılReşat I edited the answer, thanks. – mfcc64 Oct 23 '19 at 16:24