Beta. Content is under active construction and has not been peer-reviewed. Report errors on
GitHub
.
Disclaimer
Theorem
Path
Curriculum
Paths
Demos
Diagnostic
Search
Quiz Hub
/
Fast Fourier Transform
Fast Fourier Transform
3 questions
Difficulty 3-5
View topic
Foundation
0 / 3
1 foundation
2 intermediate
Adapts to your performance
1 / 3
foundation (3/10)
compute
The Fast Fourier Transform (FFT) computes the Discrete Fourier Transform. What is its time complexity compared to direct computation?
Hide and think first
A.
FFT:
O
(
n
lo
g
n
)
. Direct DFT:
O
(
n
2
)
. FFT is divide-and-conquer on the DFT matrix's structure.
B.
Both FFT and DFT:
O
(
n
2
)
. FFT is just a better constant factor.
C.
FFT:
O
(
n
)
linear time through streaming accumulation.
D.
FFT:
O
(
lo
g
n
)
through parallelization.
Submit Answer