> For Fourier, given an N-dim vector you would compute the N Fourier coefficients in Nlog(N) time

But Nlog(N) only works for certain values of N, right (like powers of two)? I guess for other cases, we could use the clipping method to dictate behavior, but that doesn't feel great.