# What is the time complexity of the Bailey–Borwein–Plouffe formula?

How can I assess and derive the time complexity of the BBP formula? $$BBP(n)=4S(1,n) - 2S(4,n) - S(5,n) - S(6,n)$$ where

$$S(j,n) = \sum_{k=0}^n{\frac{16^{n-k}mod(8k+j)}{8k+j}}+\sum_{k=n+1}^{\infty}{\frac{16^{n-k}}{8k+j}}$$

Note that the modulo is evaluated using the binary modular exponentiation algorithm (which is supposedly O(log N)) and the second sum iterates only over a few elements, i.e. up to a certain $\epsilon$.

I got O(N log N), but even if it is correct, I can't derive it.

A good place to start is the BBP paper. In Section 3 (1st paragraph of page 8) they state that the running time for $n$ digits is $O(n\log nM(\log n))$, where $M(m)$ is the complexity of integer multiplication; currently the best known algorithms give $M(m) = O(m\log m 2^{O(\log^* m)})$ bit complexity, though Fürer himself (inventor of the first algorithm with that complexity) argues that this is not the correct complexity measure.