When does complexity in machine learning algorithms actually become an issue?

I keep seeing complexities for machine learning algorithms e.g. Gaussian process implementation requires inversion of an nxn matrix so complexity is $$O(n^3)$$.

When does complexity actually become an issue? Is there a way to work out when it becomes prohibitive?

• Are you looking for guidance on $n$ for Gaussian processes in particular or more general guidelines/information on complexity and scalability? Aug 10 '21 at 9:12
• @jcken, more general guidelines please but would also appreciate info on n for Gaussian processes ! Aug 10 '21 at 9:18

I use least-squares support vector machines a fair bit, which are $$\mathcal{O}(n^3)$$ for the most obvious implementation, and problems with up to a ten thousand or so examples are just about practical on my machine, but memory usage is not insignificant either, and 8192*8192 matrix in double precision format is 0.5Gb of memory.