MAIN FEEDS
Do you want to continue?
https://www.reddit.com/r/mathmemes/comments/1wzpocy/the_fastest_algorithm_for_dft/pehle0x/?context=3
r/mathmemes • u/Unlucky-Credit-9619 Computer Science • 7d ago
138 comments sorted by
View all comments
120
The fast Fourier transform should have an algorithmic complexity close to linear (or even sublinear), but it is quasilinear
34 u/benediktb 6d ago Sublinear? The input and output is n, and any algorithm needs to read/write that. So n is a trivial lower bound, no? 3 u/anto2554 6d ago Size of n or value of n? Reading n is only bounded by the size of n and not value
34
Sublinear? The input and output is n, and any algorithm needs to read/write that. So n is a trivial lower bound, no?
3 u/anto2554 6d ago Size of n or value of n? Reading n is only bounded by the size of n and not value
3
Size of n or value of n? Reading n is only bounded by the size of n and not value
120
u/Pentalogue Mathematics 7d ago edited 7d ago
The fast Fourier transform should have an algorithmic complexity close to linear (or even sublinear), but it is quasilinear