Gaussian Process and Expectation Propagation time complexity?

Question

What's the time complexity of training a Gaussian process and its Expectation Propagation approximation?

(Before studying them, I'd like to understand if they are even feasible for my application)

Answer 1

I stumbled onto this passage in Gaussian Processes for Machine Learning, p. 24:

For the GP models it is computationally expensive to make use of all 44,484 training cases due to the $O(n^3)$ scaling of the basic algorithm. In chapter 8 we present several different approximate GP methods for large datasets.

P. 58 has some detail on the complexity of the EP algorithm, also $O(n^3)$, and chapter 8 offers several approximation methods for use with large datasets. A table of complexities for storage, initialization, and calculating predictive mean using those methods is found on p. 183.