> FFT based matrix multiplication, which is O((n^2)log(n))
What?
What?
I forgot the log(log(n)) factor.
In any case, for matrix multiplications that people actually do, this algorithm runs slower than a well optimized O(n^3) matrix multiplication implementation because the constant factor in the Big O notation is orders of magnitude larger.