Ben-Or, Kozen, and Reif (1986) proved that the theory of real closed fields is decidable in exponential space, and therefore in doubly exponential time.
EXPSPACE |