Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Appearance settings

Commit a5953a5

Browse filesBrowse files
authored
Fix sentence structure in fft.md (cp-algorithms#1408)
1 parent e0b8036 commit a5953a5
Copy full SHA for a5953a5

File tree

Expand file treeCollapse file tree

1 file changed

+1
-1
lines changed
Filter options
Expand file treeCollapse file tree

1 file changed

+1
-1
lines changed

‎src/algebra/fft.md

Copy file name to clipboardExpand all lines: src/algebra/fft.md
+1-1Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -97,7 +97,7 @@ It is easy to see that
9797

9898
$$A(x) = A_0(x^2) + x A_1(x^2).$$
9999

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$.
101101
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**.
102102

103103
Let's learn how we can accomplish that.

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.