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.