Time complexity of divide and conquer to multiply $n$ linear polynomials using FFT

21 Views Asked by At

I know that the time complexity is $$O\left(\sum^{\log_2n}_{k=0}O\left( n\log_2\left(\frac{n}{2^{k}}\right) \right)\right) = O\left( O\left( n(\log_2n)^2 \right) - \sum^{\log_2n}_{k=0}O\left( nk \right)\right)$$ Unfortunately, operations with big O notation can't work if both sides have the same growth rate and I do not know how to proceed. My friend mentioned that he read that the time complexity reduces to $O(n\log n)$ somewhere 3 years ago but is not sure, so what is the actual time complexity of this?