There is an algorithm of complexity $O((\ln n) \cdot P(n))$ where $P(n)$ is the complexity of computing the prime counting function on n (usually denoted $\pi(n)$).
By Bertrand's postulate there is a prime in the interval $[n,2n]$ so you can do a binary search on it:
If $\pi\left(n+\frac{n}{2}\right)-\pi(n)$ > 1 there is a prime in the interval $\left[n, n+\frac{n}{2}\right]$, otherwise there is a prime in the interval $\left[n+\frac{n}{2}+1,2n\right]$ and so you obtain a smaller interval that contains a prime. Repeat the calculation on the new interval. The calculation for which of the 2 intervals to use needs time $O(P(n))$. Since each interval is half the size of the previous one the total number of calculations required is O(ln n).
Odlyzko's algorithm for $\pi(n)$ has complexity $O(n^{\frac{1}{2}})$. There is a link to a short description of it on the polymath page. So the overall complexity of this algorithm is $O((\ln n)n^{\frac{1}{2}})$.