What is the scalability of linear regression and decision trees?
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&gt;&gt;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)