# Gaussian Process and Expectation Propagation time complexity?

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)

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.