Can FFT convolution be faster than direct convolution for signals of large sizes?
There is probably a bit of a misconception here. In many application the signal is  runnning all the time or is VERY long: modem, audio stream, video etc. In this case you can't really define the &quot;length&quot; of the signal. The relevant metric is here &quot;number of operations per input sample&quot; not the &quot;total  number of operations&quot;. If you watch a streaming movie, it's obvious that a two hour movie takes twice the operations of a one hour movie. But that's okay since you have twice the time to process it. The key metric is if your processor can keep up with the stream , so that's why &quot;ops per sample&quot; or &quot;ops per second&quot; are used.
In this case, you don't do an FFT over the entire input signal but you apply &quot;overlap add&quot;, i.e. you chop the input signals into blocks that are about the same size as the filter length and then you process one block at a time.
So the effectiveness of the algorithm is only a function of the filter length. And it increases linearly for direct convoltuion but only logarithmically for Overlap Add (which is FFT based). The &quot;break even&quot; point is typically at &quot;many tens of samples&quot;.
We can run some numbers assuming that the filter length is $N$ and lets also assume its a power of 2.
An FFT of length $M$ has  $log_2(M) \cdot M/2$ butterflies, each with one complex multiplies and two complex adds. That's a total of 10 real operations. So the price for an FFT is roughly $5 \cdot log_2(M) \cdot M/2$
Overlap add requires zero padding to 2N and that's our FFT size. Hence overlap add costs

Forward FFT: $5 \cdot log_2(2N) \cdot 2N/2$
Spectral Multiply: $3*N$  (N/2 complex multiplies)
Inverse FFT: $5 \cdot log_2(2N) \cdot 2N/2$
Overlap adding: $N$
Total: $N\cdot (10 \cdot log_2(N) + 10 + 3 + 1)$

So overlap add cost per sample is roughly $ 10 \cdot log_2(N) + 14$ as compared to $2N$ for direct convolution. The break even point is a filter length of 32.
DISCLAIMER: I made a lot of simplying assumptions and in a practical implementation the break even point can vary wildly based on processor architecture and smartness of the algorithm. The main cost is in the FFT and for a single channel real system you would deploy a core complex FFT of N/2. I also skipped over bit reverse ordering and other overheads.