# Analysis and algorithmic complexity of the Constant Q transform

Here I am again (Implementation of the constant Q transform + property questions) :)

I was reading this paper on a constant-q transform algorithm, where they managed to turn the following equation for the constant-q transform: into this: (where X[k] is the fourier transform of x[n], and K*[k, kcq] is the complex conjugate of the fourier transform of the w[n, kcq]) - claiming it to be an efficient algorithm.

While I'm still new to algorithmic complexity, I tried to derive the big-O complexity. I'm assuming the transforms of the windows (ie. K*[], the kernels) are pre-calculated. Let N be the size of the transform, and K the number of components (kernels / filters / results). Would this be correct? So thats the FFT (N * log2(N)) plus K loops of N multiplies (the convolution) + additional stuff done at each loop (done K times). Also, since the kernels are precalculated, that incurs both a certain amount of memory storage needed + a lot of memory access during the calculation. With their implementation, they store the kernels in full size (that is, N), so the required storage memory for the calculation would be K kernels of N size.

I'm defining M() to be the amount of memory used during an calculation: That is, we need to load the whole signal (N), also K number of N-sized complex (2) kernels. That is quite different from algorithms like the standard fft and direct evaluation of the constant-q transform which requires no working storage, and as of such are defined to be:  -Since they only need to load the signal. If we define the complexity of the FFT and the direct evaluation of the constant-q transform to the following: (This assumes direct evaluation of the CQ-transform which incurs at least NK operations, together with NK operations calculating the discrete window for each component.) we can create a small comparison table for an example. If the transform is of size 2048, and the wanted number of components is 1048 (N = 2048, K = 1048), we get the following results: It would seem the cqfft algorithm (theirs) incurs a rather extreme memory cost (that in practical appliances could dominate computational speed) for a mere ~2x increase in computation speed. Is this correctly derived?

Here's a reference-pseudocode of their implementation i wrote, as i understand it. If i have misunderstood their algorithm, it will probably show here:

std::vector<complex<float>> fft(float[], size_t);

class kTransform
{
vector<complex<float>> cqfft(vector<float> signal)
{
vector<complex<float>> fftdata = fft(signal, size);
for (int kernel = 0; kernel < kernels.size(); ++kernel)
{
complex<float> accumulator;
for (int k = 0; k < size; ++k)
{
accumulator += fftdata[k] * conj(kernels[kernel][k]);
}
fftdata[kernel] = accumulator / size;
}
return fftdata;
}

void compileKernels(vector<float> freqs, size_t dftSize)
{
auto numKernels = freqs.size();
kernels.resize(numKernels);
size = dftSize;
for (int kernel = 0; kernel < numKernels; ++kernel)
{
kernels[kernel] = fft(Window(freqs[kernel]));
}
}
size_t size;
vector<vector<complex<float>>> kernels;
};


Thank you for any insight. As a bonus question, does anyone know what the complexity of a fast implementation of the Gabor transform is?