I have read that the exact number multipications in radix 2 computation is $\frac{N}{2}\log_{2}N$ and I am trying to understand why.
Let $x[n]$ be a sequence of length $N$ where $N = 2^l$ for some $l\in \mathbb{N}$. I want to calculate the DFT of $x[n]$ using FFT radix 2 algorithm. So basically, as I understand, what we do is dividing $x[n]$ into its even elements, call this sequence $e[n]$ of length $N/2$, and odd elements, call this sequence $o[n]$ also of length $N/2$.
And we have $X[k]$ = $E[k] + W_{N}^{-k}O\left[k\right] $ where $X[k]$ is the DFT of $x[n]$, $E[k]$ is the DFT of $e[n]$, $O[k]$ is the DFT of $o[n]$ and $W_{N}^{-k}$ is the twiddle factor which is given by $ e^{-j\frac{2\pi}{N}k}$. Further more since $ W_{N}^{-k}=-W_{N}^{-\left(k+\frac{N}{2}\right)} $ it is enough to multiply the twiddle factor by $O[k]$ for $k \leq N/2$.
Now, assume the time complexity of the FFT is $T[N]$. We have shown that $ T\left[N\right]=2T\left[\frac{N}{2}\right]+\frac{N}{2} $ where the $2\cdot T[N/2]$ is due to the FFT we need to calculate for the odd and even sequences of X and the $N/2$ is due to the multipications of the twiddle factor by the odd sequence.
Now, using the recursive equation we get $$ T\left[N\right]=2T\left[\frac{N}{2}\right]+\frac{N}{2}=2\left(2T\left[\frac{N}{4}\right]+\frac{N}{4}\right)+\frac{N}{2}=2^{2}T\left[\frac{N}{2^{2}}\right]+2\frac{N}{2} $$
$$ =2^{2}\left(2T\left[\frac{N}{2^{3}}\right]+\frac{N}{2^{3}}\right)+2\frac{N}{2}=2^{3}T\left[\frac{N}{2^{3}}\right]+3\frac{N}{2}=...=2^{\log_{2}N}T\left[\frac{N}{2^{\log_{2}N}}\right]+\log_{2}N\cdot\frac{N}{2} $$
$$ =NT\left[1\right]+\log_{2}N\cdot\frac{N}{2} $$
$$ =N+\log_{2}N\cdot\frac{N}{2} $$
Assuming of course that one multipication is one unit of calculation time.
What am I missing here?
Obviously this is still $O(N \log (N)$ but I am intrested in the exact number of multipications.