For $2 \leqq c \leqq \infty $, the c-linear complexity $L_c (A)$ of a complex matrix A is defined as the minimal number of additions, subtractions, and multiplications by complex constants of absolute value $ \leqq c$, sufficient to evaluate A at a generic input vector. It is shown that if A is a Fourier transform on the finite group G, then $| L_\infty (A) - L_\infty (A^{ - 1} ) | \leqq | G |$. $L_c (G): = \min \{ L_c (A)|A{\text{ a Fourier transform for }}G\} $ is called the c-linear complexity of the finite group G. It is proved that $L_2 (G) > \frac{1}{4}| G |\log | G |$ for any finite group G, and two infinite classes of non-abelian groups G with $L_2 (G) \leqq 0.6| G |\log | G |$ and $L_2 (G) \leqq 0.8| G |\log | G |$, respectively, are presented. Thus there are non-abelian groups with even faster Fourier transforms than elementary abelian 2-groups (for which $L_2 (G) \leqq | G |\log | G |$)!