i was looking into the FFT and watching the wonderful Videos of Prof. Strang's MIT 18.06 Linear Algebra Series and came upon Vid.26 where at the end (43 min mark) the time complexity of the FFT in matrix form is given as $ \mathit{O}(n\log_2n)$.
Which is because the FFT Matrix $F_N$ can be written as
$$ \begin{bmatrix} F_{N} \end{bmatrix} = \begin{bmatrix} I & D_{N/2} \\ I & -D_{N/2} \end{bmatrix} \begin{bmatrix} F_{N/2} & 0 \\ 0 & F_{N/2} \end{bmatrix} \begin{bmatrix} P_{N} \end{bmatrix} $$
Where the matrix multiplications by $D_{N/2}$ are of complexity $ \mathit{O}(n/2)$, by the two $F_{N/2}$ matrices of complexity $ \mathit{O}(n^2)$ and by $I, P_N$ are trivial.
Therefore the complexity for calculating the FFT for $F_{64}$ for example can be simplified from $ \mathit{O}(64^2) $ to $ \mathit{O}(2(32)^2+32) $.
I tried to work with a smaller n in order to make things more clear and chose $n=8$ for which $F_8$ can be simplified from $8^2$ to
$$ 2(4)^2+4 \, \to 2\left[2(2)^2+2\right]+4 \, \to 2\left[2\left( 2(1)^2+1 \right)+2\right]+4 $$
So after simplification we get $2^3 + 3(4)$ which can be generalized to $2^{log_2n} + log_2n \cdot \frac n2 = n + \frac n2 log_2n$
Is this the same as $ \mathit{O}(n\log_2n)$ or did I make a mistake in here?