So it is known that the complexity of DFT is $O(n^2)$ and of FFT is $O(nlog_2 n)$.
However in my material, it is stated that the worst-case complexity of DFT is $O(n^2)$ only if $n$ is a prime number. So I am wondering what difference $n$ makes if it is a prime, and what would the complexity be if it is not a prime number?
We know that FFT goes when $n = 2^k$, but an example is if $n=6$, this is not a prime number and there is no $k$ such that $n=2^k$, so what is the complexity in that case?
The magical characteristic of the Fast Fourier Transform is that it turns a product of factors in a sum of factors
$$N=p\cdot q\to (p+q)N$$ $$N=2^n\to (n\cdot 2)N=2N\log_2N$$ $$N=p^mq^nr^k\cdots\to(mp+nq+kr+\cdots)N$$
because the whole process can be decomposed as a sequence of stages of complexity $pN$ where $N$ is the number of coefficients and $p$ a factor of $N$.
Prime $N$ indeed make it quadratic $O(N^2)$.