FFT Algorithm: Fast Fourier Transform—Big-O vs Precision ⚡
Learn the FFT algorithm: fast Fourier transform, big O vs real runtime. Understand algorithm complexity, numerical precision, and hidden constants—check before you ship.
A Faster FFT on Paper Is Not Necessarily Faster on Your Computer
The Fast Fourier Transform is one of those algorithms that quietly makes modern computing possible. It helps process audio, images, wireless signals, and scientific data without forcing you to do an expensive calculation from scratch for every frequency. So when someone claims a "faster FFT," it's worth pausing and asking the obvious question: faster under what assumptions?
A recent OpenAI mathematics result was presented as a faster Fourier transform. The interesting part is the theoretical running-time claim. The practical worry is that the result appears to rely on a model of computation that looks very different from what engineers actually run: one that treats complex arithmetic as exact and arbitrarily precise. On top of that, the constants look so large that any asymptotic advantage may never show up in practice.
This isn't just nitpicking. The gap between "an algorithm that works well" and "a theorem about an abstract machine" is exactly where people get misled. In this article, I'll walk through what the FFT is doing, how to interpret the claim, why big-O can be a poor proxy for real speed, and what you should check before treating a theoretical speedup like an engineering breakthrough.
What the FFT does - and why it matters
A Fourier transform breaks a signal into frequency components. If you have a recording, it can show how much low-frequency rumble, speech-range energy, or high-frequency detail is present. The same basic operation shows up in image processing, communications, simulation, and data analysis.
For a discrete signal with n samples, the direct method computes the contribution at each of n frequencies. Each frequency calculation runs through all n input samples. That's about n2 arithmetic operations. It's fine for small inputs, but it blows up fast: multiply the input size by ten and you multiply the work by about one hundred.
The Fast Fourier Transform, or FFT, is a way to avoid redoing a lot of that work. The Cooley-Tukey approach breaks the transform into smaller transforms, combines the results, and repeats the process. When the input size fits the method's assumptions, the operation count is typically described as O(n log n) rather than O(n2).
The practical value of the standard FFT
That difference matters in the real world. A direct transform on a million samples is on the order of a trillion pairwise operations. An FFT still does work that grows with n, but much more gently - roughly proportional to n log n. Exact runtime depends on implementation details, hardware, data layout, and input length, but the growth-rate change is the reason FFTs are so widely used.
That said, "FFT" doesn't automatically mean "fast on your machine." Real systems have cache effects, vector instructions, memory bandwidth limits, and error/accuracy constraints. Libraries often use different strategies depending on input size, and those details can matter more than shaving a bit off an abstract operation count.
The lower-bound question
Once an algorithm is already O(n log n), it's natural to ask whether you can make it faster. A tempting target is O(n), since the output has n values and you have to at least write them somewhere. But output size alone doesn't guarantee a linear-time transform exists: the cost depends on how each output value depends on the input, and on the computational model you assume.
The key point is that "faster" can mean different things. You can ask about better asymptotic operation counts. You can ask how quickly an actual program runs for input sizes you can realistically handle. Or you can ask whether the method gives accurate results within practical limits on time, memory, and numerical error. These questions overlap, but they aren't the same.
What a theoretical speedup actually says
Big-O notation describes how a function grows as inputs get large. If a running time T(n) is O(F(n)), the meaning is: there exist constants C and N such that for all inputs larger than N, T(n) ≤ C · F(n).
That definition is useful because it lets researchers compare growth rates without locking every result to a specific processor or software implementation. It also hides details on purpose. The constant C and the threshold N aren't shown in the notation, and for real performance they can dominate.
Why the hidden constant changes the result
Say you have two hypothetical algorithms. One takes 10,000n steps. Another takes n log n steps. The second grows more slowly for larger n, but it isn't automatically faster for the inputs you actually care about. The crossover point depends on the constants and the lower-order work. If the constant multiplying the better asymptotic bound is huge, the "win" might only happen at input sizes you'll never reach.
People sometimes call these "galactic" algorithms - results whose advantages show up only at absurdly large inputs. It's a fun phrase, but the underlying issue is ordinary engineering: an asymptotic bound isn't a benchmark.
The critique of the OpenAI result argues that the hidden constants are extraordinarily large. It suggests that even for very large inputs, the conventional Cooley-Tukey FFT would stay dramatically faster. The exact numbers depend on the paper's construction and how its model is interpreted. The broader takeaway doesn't depend on one estimate: if a result doesn't provide a usable constant/threshold/resource analysis, the asymptotic claim alone can't tell you when it will beat existing software.
A smaller logarithm is not a performance guarantee
Sometimes a "faster" result comes from reducing a factor inside the running-time expression - for example, replacing one logarithmic term with something that grows more slowly. That can be a real mathematical improvement. But it doesn't mean the proposed method will be faster for audio files, scientific arrays, or any other input sizes a user can realistically produce.
To know whether it's faster in practice, you need more than the leading term. You need the full algorithm, a clear accounting of operations, realistic constants, and a like-for-like comparison under the same assumptions as the baseline. Ideally you also want an implementation and measurements. Without those, the safest interpretation is limited: the result might establish something about an abstract model, not about what runs quickly on a laptop or a signal-processing pipeline.
The gap between the mathematical model and real computers
A big part of the critique is the model of computation. The reported method assumes exact complex arithmetic, including operations on numbers with arbitrary precision. In that model, multiplying two complex values counts as one operation no matter how many bits you'd need to represent those values.
That's a legitimate abstraction for some kinds of math questions. It's not how hardware behaves. Real computers use finite representations, and the cost of arithmetic can rise when operands get larger. If values grow to very large magnitudes or require extreme precision, you pay in memory and processing time. You can also run into numerical issues that simply don't show up in a model where everything stays exact.
What changes when numbers need many bits
Imagine an algorithm that produces intermediate complex values whose magnitudes explode as the input grows. If those values need more bits to represent, then "one arithmetic operation" is no longer a fixed-cost event. You might still have a favorable count of abstract operations, while each one becomes expensive. Storage can become a bottleneck too.
That's why "one multiplication" needs context. Multiplying two machine-sized floating-point numbers isn't the same as multiplying arbitrary-precision integers or complex numbers represented with millions of bits. A complexity result that counts both as one step may answer a coherent theoretical question, but it doesn't directly estimate runtime for normal software.
The same caution applies to numerical stability. A method might produce a number, but "produces a number" doesn't guarantee the number is accurate enough for your application. Some signal-processing tasks can tolerate rounding error; other domains (like certain scientific or financial calculations) can't. A useful analysis should say what precision is required and whether the method can reach it without ballooning the cost.
The history of restrictions matters
There's a long line of work studying lower bounds for Fourier transforms under different assumptions. The source article points to work by Jacques Morgenstern, including a lower bound in a restricted coefficient model, and later work by Nir Ailon connecting faster computation to numerical instability. Restrictions matter because a lower bound is only as broad as the model it's proved in.
It's also reasonable to ask whether a model is too restrictive. The point isn't that one model is "the" correct one for everything. The point is that relaxing a restriction changes the question. If a new result escapes an old lower bound by allowing coefficients with unbounded magnitude or exact arithmetic, that can be a real theoretical advance. But it still doesn't automatically solve the engineering problem the original bound was meant to illuminate.
You can lose sight of that distinction when a paper gets summarized as "a faster FFT." A headline like that suggests a new implementation, but the result may instead be a statement about what's possible on a machine that doesn't resemble your server rack.
How to evaluate a claimed algorithmic breakthrough
If a result claims a dramatic speedup, you don't have to dismiss it or swallow the headline. Identify the exact claim first. Then trace the assumptions to the practical consequences. That approach is more useful than arguing whether the result is "real" in the abstract.
1. Identify the computational model
Start with: what counts as one operation? Does the analysis assume exact real/complex arithmetic? Are numbers bounded in magnitude? Does the cost include handling larger bit-lengths? Are memory access and data movement part of the accounting?
Those choices determine what the theorem is actually saying. A result proven in an exact-arithmetic model can be mathematically interesting while offering little direct guidance for finite-precision code. Neither conclusion cancels the other - they just refer to different systems.
2. Read the whole complexity statement
Look for the constants, lower-order terms, and thresholds that big-O suppresses. If the paper gives only an asymptotic bound, it doesn't establish a practical crossover point. If the constants are hard to estimate, that uncertainty should remain visible instead of being glossed over with optimism.
Also check whether the bound applies to the complete computation or only a part of it. An algorithm can reduce arithmetic operations while increasing memory usage, preprocessing, or data movement. In production systems, the "slowest" resource isn't always the one counted by the theorem.
3. Check whether the algorithm is explicit and implementable
A concrete algorithm should explain what steps to run, what resources it needs, and which input sizes it can handle. A proof that "some algorithm exists" isn't the same thing as an implementation engineers can build and test. If the construction is too complex to reproduce or relies on parameters that you can't estimate usefully, then the path from theorem to software is still open.
This isn't only a Fourier-transform issue. Similar questions show up in fast matrix multiplication and other results where a better exponent gets reported. Even when the exponent improves, the construction can stay impractical due to constants, memory requirements, or sheer implementation complexity.
4. Compare like with like
A practical performance claim needs a fair baseline. Use the same inputs, accuracy requirements, hardware, and measurement conditions. Compare against mature FFT libraries, not only naive implementations. Include setup costs and memory use when your application pays those costs. Measure across multiple input sizes too - an algorithm's advantages might only appear in a narrow range.
If the result isn't implemented, say so. That's not an insult to the theory; it's just a clear statement of current status. The research can still motivate future work, but readers shouldn't confuse "promising in principle" with "faster for users today."
5. Separate mathematical value from product value
A theorem can advance understanding even if it doesn't yield faster software. And a modest engineering improvement can matter a lot for a product even if it doesn't change asymptotic complexity. Those are different kinds of value, and both can be worthwhile.
One practical way to frame the decision is to tie it to your purpose:
- If you're doing complexity theory, does the result establish a new bound in a clearly stated model?
- If you're building a system, does it reduce runtime, memory, or cost at your real input sizes?
- If you're deciding whether to invest in implementation, is there a credible path from the construction to finite-precision hardware?
This framing helps avoid two common mistakes: treating every theoretical result as a shippable breakthrough, and dismissing theory simply because it isn't immediately deployable.
Conclusion: judge the model, not just the bound
A claim of a faster Fourier transform deserves a closer look, but the asymptotic label is only step one. The real questions are: what counts as an operation, how large the hidden constants are, whether the arithmetic model matches finite-precision hardware, and whether anyone can actually implement it and benchmark it at useful input sizes.
The reported OpenAI result may be interesting as a statement in theoretical computer science. Based on the critique summarized here, it shouldn't be treated as a faster FFT for real computers without evidence of a practical implementation and a credible cost model. That isn't a knock on theory. It's a reminder to keep the theorem and the engineering claim separate.
When you run into the next algorithmic breakthrough, check the model, the constants, the precision assumptions, and the crossover point before redesigning your system. For more detail, read the original discussion of the faster Fourier transform.