# What is the Big-Oh asymptotic complexity of learning in Random Forests?

Random Forests is a bagged ensemble of CART learners. The following is what I've found, but am not sure if I'm completely right.

CART (Classification and Regression Trees) uses the Gini index for splitting (whereas Shannon's Entropy function is used in ID3). From what I know, it's asymptotic complexity can be represented as $O(n \log n)$, where $n$ is the number of samples and $m$ is the number of attributes.

Assuming $M$ to be the number of trees in a Random Forest, it's asymptotic complexity ought to be $M$ times that of CART, hence $O(Mnm \log n)$. This is neglecting the constant factors that scale linearly such as random selection of features for each tree of the forest.

Is this notion correct? Or is there more to this?

• The asymptotic complexity of what operation? – David Richerby Nov 16 '16 at 11:10
• @DavidRicherby: Sorry, I meant the complexity of learning. Just added the same in the question title. – Ébe Isaac Nov 16 '16 at 11:56
• The question is still unclear. You write "it's asymptotic complexity"; well, the complexity of what? Complexity can only be applied to algorithmic tasks (the task of computing some output given some input), but what precisely is the task here you want to know the complexity of? This affects the correct answer. Also, you've overlooked a complication: the learner must choose a threshold at each node (so at least naively one might need to consider all possible thresholds). Are you dealing with boolean/categorical attributes, or numerical/continuous attributes? – D.W. Nov 16 '16 at 16:17
• Finally, note that random forests does not consider all $m$ attributes at each node it builds; it uses only a small subset. You might want to read more about standard algorithms for random forests. See, e.g., en.wikipedia.org/wiki/…. What reading and self-study have you already done? Right now the best answer I can give in a reasonable amount of space is "no, this is not correct, you have some misconceptions, the best advice I can give is to read up more on how random forests learning works". – D.W. Nov 16 '16 at 16:19
• @D.W.: It is actually a collection of all of the above, but for simplicity, we could consider only numerical features. I've successfully applied Random Forests (in Weka, although I understand enough to be able to code it myself) for classification in a dataset and would like to know its algorithmic analysis. The params. were no. of trees, $I$, max. depth $d$, and no. of rand. features selected for each tree, $K$ (I took this as $m$ for this question, I didn't actually mean all available attributes). The input consists of the $n$ samples with $d$ features, while the output is the trained model. – Ébe Isaac Nov 16 '16 at 16:30