3 ms·

:-) It seems Cooley and Tukey were the first to realize/state that it's O(N log N), which is something.