1 of 6

Where does the lg(lg(N)) factor come from in Schönhage–Strassen's run time?

According to page 53 of Modern Computer Arithmetic (pdf), all of the steps in the Schönhage–Strassen Algorithm cost $O(N \cdot lg(N))$ except for the recursion step which ends up costing $O(N\cdot lg(N) \cdot lg(lg(N)))$.

I don't understand why the same inductive argument used to show the cost of the recursive step doesn't work for $O(N\cdot lg(N))$.

  • Assume that, for all $X < N$, the time $F(M)$ is less than $c \cdot M \cdot lg(M)$ for some $c$.
  • So the recursive step costs $d \cdot \sqrt{N} F(\sqrt{N})$, and we know this is less than $d \cdot \sqrt{N} c \cdot \sqrt{N} lg(\sqrt{N}) = \frac{c \cdot d}{2} \cdot N \cdot lg(N)$ by the inductive hypothesis.
  • If we can show that $d < 2$, then we're done because we've satisfied the inductive step.
  • I'm pretty sure recursion overhead is negligble, so $d \approx 1$ and we have $\frac{c}{2} N \cdot lg(N)$ left to do the rest. Easy: everything else is $O(N \cdot lg(N))$ so we can pick a $c$ big enough for it to fit in our remaining time.

Basically, it looks like things would work out if we assumed the algorithm costs $O(N \cdot log(N))$... so where is the penalty coming from?

My best guess is that it has to do with the $lg(lg(N))$ levels of recursion, since that's how many times you must apply a square root to get to a constant size. But how do we know each recursive pass is not getting cheaper, like in quickselect?

For example, if we group our $N$ initial items into words of size $O(lg(N))$, meaning we have $O(N/lg(N))$ items of size $O(lg(N))$ to multiply when recursing, shouldn't that only take $O(N/lg(N) \cdot lg(N) \cdot lg(lg(N)) \cdot lg(lg(lg(N)))) = O(N \cdot lg(lg(N)) \cdot lg(lg(lg(N))))$ time to do.

Not only is that well within the $N \cdot lg(N)$ limit, it worked even though I used the larger $N\cdot lg(N)\cdot lg(lg(N))$ cost for the recursive steps (for "I probably made a mistake" values of "worked").