0
$\begingroup$

http://www.jstor.org/stable/2003354?seq=5#page_scan_tab_contents

In the original algorithm of Cooley Tukey it says that in page 298 (11) and (12) the total number of operations is T(r) = rNlogN/logr.

But in many books and references it says NlogN only. What is the difference here?

$\endgroup$
  • $\begingroup$ hsm.stackexchange.com might be a better candidate. This is not really about mathematics. $\endgroup$ – copper.hat Dec 6 '17 at 18:07
  • $\begingroup$ What is $r$ ? Usually the complexity of the FFT is the number of multiplications+additions of a certain precision. $\endgroup$ – reuns Dec 7 '17 at 13:55
  • $\begingroup$ r is the radix, here it can be 2 $\endgroup$ – Hüseyin Kömürcü Dec 7 '17 at 16:17
0
$\begingroup$

Because they originally assumed the complexity of butterfly as 4 complex multiplications. They multiply all entries with complex twiddle factors.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.