What is the computational complexity of calculating $\pi(x)$ exactly? The prime counting function $\pi(x)$ has been determined for $x=10^{26}$.
The list of the $10^n$-th primes , however , ends at $n=18$. The $10^{18}$-th prime has $20$ digits.
Apparantly, the determination of $\pi(x)$ is easier than the determination of $p_n$ (the $n$-th prime).

What is the computational complexity of determining $\pi(n)$ exactly ?
What is the computational complexity of determining the $n$-th prime ?
Is the second problem actually harder than the first ? (I think this is not the case because with binary search, it should be possible to determine $p_n$ nearly as efficiently as the determination of $\pi(n)$)

It is true that the problem is not of great practical interest because $li(x)$ is a very good approximation of $\pi(x)$. I am just curious how far the exact calculation could go on with the current computational power available.
 A: Right now there are two competing methods for determining $\pi(x)$ when $x$ is large: the combinatorial method of Meissel-Lehmer-Lagarias-Miller-Odlyzko-Deleglise-Rivat (see here), which requires $O(\frac{x^{\frac{2}{3}}}{(\log x)^2})$ time and $O(x^{\frac{1}{3}}(\log x)^2)$ space, and the analytical method of Lagarias-Odlyzko (see here), which requires $O(x^{\frac{1}{2}+\epsilon})$ time and $O(x^{\frac{1}{4}+\epsilon})$ space. (Although actually, the latter method can be modified to require $O(x^{\frac{3-2\delta}{5}+\epsilon})$ time and $O(x^{\delta+\epsilon})$ space for $0 \le \delta \le \frac{1}{4}$.)
Interestingly, the record of $\pi(10^{26})$ was obtained using the combinatorial method, which is slower asymptotically; perhaps the crossover point has not yet been reached.  Another factor is likely the difficulty of implementing the analytical method.
As you say, we can use $\pi(n)$ to determine $p_n$, and the computational complexities will not be much different asymptotically; however, the difference is likely enough to cause $p_n$ to lag behind, since we would need to evaluate $\pi(n)$ many times just to determine one value of $p_n$.  But, I would say that the difference of a factor of $10^6$ between the two records is probably due to less attention paid to $p_n$.
A: According to Kim Walisch's benchmark Xavier Gourdon's method is the faster.
Its time complexity is  $O(\frac{x^{\frac{2}{3}}}{(\log x)^2})$ which seems to be same as Deleglise-Rivat's, but performs better due to constant optimizations.
Time Complexity over time:
1798 : Legendre => $O(n^{3/4})$
1870 : Meissel => $O(n^{2/3}.log^{1/3}n)$
1959 : Lehmer => $O(n^{2/3})$ — popularly known as Missel-Lehmer
1985 : Lagarias, Miller and Odlyzko => $O(n^{2/3}/log\ n)$ — popularly known as LMO
1996 : M. Deleglise, J. Rivat    => $O(n^{2/3}/log^2n)$
2001 : Xavier Gourdon => $O(n^{2/3} / log^2n)$ (constant factor for both time and memory improved) — default algo for Kimwalisch's package
2015 : Douglas Staple => $O(n^{2/3} / log^2n)$ (constant factor for memory improved)
