What is the time complexity of the Bailey–Borwein–Plouffe formula?
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.