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").