You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: src/algebra/fft.md
+1-1Lines changed: 1 addition & 1 deletion
Original file line number
Diff line number
Diff line change
@@ -97,7 +97,7 @@ It is easy to see that
97
97
98
98
$$A(x) = A_0(x^2) + x A_1(x^2).$$
99
99
100
-
The polynomials $A_0$ and $A_1$ are only half as much coefficients as the polynomial $A$.
100
+
The polynomials $A_0$ and $A_1$ have only half as many coefficients as the polynomial $A$.
101
101
If we can compute the $\text{DFT}(A)$ in linear time using $\text{DFT}(A_0)$ and $\text{DFT}(A_1)$, then we get the recurrence $T_{\text{DFT}}(n) = 2 T_{\text{DFT}}\left(\frac{n}{2}\right) + O(n)$ for the time complexity, which results in $T_{\text{DFT}}(n) = O(n \log n)$ by the **master theorem**.
0 commit comments