What is the big O notation of the Bailey–Borwein–Plouffe algorithm (n-th hexadecimal digit of Pi)?

Question

If I want to compute the n-th hexadecimal digit of Pi with http://en.wikipedia.org/wiki/Bailey-Borwein-Plouffe_formula

what is the big O notation http://en.wikipedia.org/wiki/Big_O_notation

for the Bailey–Borwein–Plouffe algorithm?

Answer 1

In the paper the upper bound of O(n log^3(n)) bit complexity is presented for calculations of the digits of log(2). Since they present a more generic formula later on, which also covers pi, I would think that it won't differ much from the above upper bound. But I haven't verified that.