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?
Because they originally assumed the complexity of butterfly as 4 complex multiplications. They multiply all entries with complex twiddle factors.