The 2-linear complexity L₂(G) of a finite group G is the minimal number of additions, subtractions and multiplications (by complex constants of absolute value ≤ 2) needed to evaluate a suitable Fourier transform corresponding to G. We prove that L₂(G) > 1/4|G| log|G| for any finite group G, and present two infinite classes of non-abelian groups G with L₂(G) ≤ 0.6|G| log|G| and L₂(G) ≤ 0.8|G| log|G| , respectively. Thus there are non-abelian groups with even faster Fourier transforms than elementary abelian 2-groups (for which L₂(G) ≤ |G| log|G|) !