What is the scalability of linear regression and decision trees?

Recently I'm studying machine learning algorithms among them linear regression and decision tree so I have a question regarding the scalability of both algorithms. Can anyone provide what is the scalability of both algorithms and examples?

• What exactly do you mean when you say "scaleability"? Apr 15, 2020 at 15:20

If you use the standard OLS formula :

$$\beta = (X^TX)^{-1}X^Ty$$

the overall linear regression complexity is $$O(np^2)$$, where n is the number of exemple and p the number of features.

For simple trees the theoretical complexity if of the same order $$O(np^2)$$.

In practice other techniques are used, like gradient descent for the regression. Also you may have simplifications depending on your problem ($$n>>p$$ for exemple, may lead to the use of sparse matrices).

Practical implementation like sklearn have following complexities (see https://www.thekerneltrip.com/machine/learning/computational-complexity-learning-algorithms/):

LinearRegression : $$O(n^{0.72}p^{1.3})$$

ExtraTreesRegressor: $$O(n^{1.03}p^{0.88})$$

Overall they are relatively simple algos and thus are pretty much as scalable as you can get. (or conversely we wouldn't use algorithms that are not scalable)

• Good explanation for the performance part. What about prediction capability. Please also add that point. Apr 16, 2020 at 5:04
• It’s an entirely different question than what was asked. There is no general answer as prediction capabilities entirely depends on your problem / data set. Intuitively they are the simplest models so their prediction capability is expected to be lower than other models. Apr 16, 2020 at 5:58