Is it possible to calculate a single frequency bin in $O(\log N)$ time (considering the $N\log N$ performance of FFT algorithms)? Fast Fourier transform (FFT) algorithms are able to calculate the discrete Fourier transform (DFT) in only $O(N\log N)$ asymptotical time. Since there is roughly $N\log N$ operations for computing $N$ frequencies, computing a single frequency takes basicly $\frac{N\log N}{N} = \log N$ operations. 
Now, is it really possible to calculate just a single frequency with $\log N$ operations? Or is the speed-up of FFT somehow "hidden" into a bigger structure?
 A: In $O(\log N)$ time—If you hypothetically could scale up the number of computational units so that they are proportional in amount to the number of elements in your series, then yes. But who has such a magical system, anyway?
In $O(\log N)$ operations—No. Your Fourier component will depend on all numbers in your series (according to the definition of the Fourier transform), so you will have to process all of the elements, which requires $O(N)$ operations.
To put it simply, what enables FFT to achieve fewer than $O(N^2)$ operations when computing all frequency components is the fact that it re-uses computations made for one frequency component for other frequency components as well.
A: Yes it is possible - if you have for example $N$ computational units, you can in $2$ units of time calculate one factor, this makes for $2\log(N)$ for all factors, since there are $\log(N)$ of those.
But, as mentioned you will need proportional to $N$ equally fast "cores" / computational units where $N$ equals signal size. And then you won't get just one frequency but all of them.
So for example a graphics card with thousands of cores or an FPGA you can probably do it if your signal size is somewhat small maybe a few $100$ to a few $1000$. But on anything with just one computation at a time, then as others have said the answer is no.
