Is it possible to reduce the complexity of radix-2 FFT if the input vector contains identical elements?
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.