Quelle est la classe de complexité de ce problème : trouver la $n$-ième décimale de $\pi$, et pourquoi ?

Réponse publiée sur Quora

En base 2 ou base 16, c’est $O(n.log(n)^3)$ en utilisant la fabuleuse Formule BBP

En base 10:

aucune formule réellement efficace n’a été découverte pour calculer le n-ième chiffre de π en base 10. Simon Plouffe a mis au point en décembre 1996 , à partir d’une très ancienne série de calcul de π basée sur les coefficients du binôme de Newton , une méthode pour calculer les chiffres en base 10, mais sa complexité en $O(n^3.log(n))$ la rendait en pratique inutilisable. Fabrice Bellard a bien amélioré l’algorithme pour atteindre une complexité en$O(n^2)$, mais cela n’est pas suffisant pour concurrencer les méthodes classiques de calcul de toutes les décimales.