Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now
2 of 6 edited body

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(X)$ is less than $c \cdot X \cdot lg(X)$ 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 negligible, 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))$. The same thing seems to happen if I expand the recursive invocations then sum it all up... 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").