Why are Decision Trees not computationally expensive?

In An Introduction to Statistical Learning with Applications in R, the authors write that fitting a decision tree is very fast, but this doesn't make sense to me. The algorithm has to go through every feature and partition it in every way possible in order to find the optimal split. For numeric features with $n$ observations, this could result in $n$ partitions for each feature.

Am I misunderstanding how the binary splitting works? Or is there a reason that this algorithm would not take long?

• +1 for the question. You can start to check this lecture note, page 15, use $O(N)$ instead of $O(N^2)$ algorithm. Jul 24, 2017 at 2:09

Decision trees algorithms do not compute all possible trees when they fit a tree. If they did they would be solving an NP-hard problem. Decision tree fitting algorithms typically make greedy decisions in the fitting process—at each stage they optimize the sub-problem for finding an optimal split with the data in the given node and the keep moving forward in the fitting process. Also, as you move deeper into the decision tree you have a smaller set of data that has made it to the given node so that you will be optimizing the splitting rule over a smaller subset of data. All of these choices are linear scans of the data in the given node. This is not complicated to do but can become somewhat expensive computationally if you have a large number of observations or a large number of covariates to split on. However, a lot of the work can be split up and sent off to different machines to work on so there are ways to build out your computational architecture to scale up. In general though, the method works fairly quickly on lots of the datasets you see in coursework and in many real world scenarios as well.

• In other words, it's more or less comparable to a binary search. Jul 24, 2017 at 15:35
• @Robert Harvey, I don't think that by optimizing the impurity functions in the fitting process you are guaranteeing or even encouraging balanced splitting. To get the binary search equivalent $log_2(N)$ search complexity you would need to enforce or at least encourage the balanced splitting. Jul 24, 2017 at 16:41
• Agreed, but the principle still holds. (That's why I used the words "more or less") Jul 24, 2017 at 16:43
• so what is the time complexity for a non distributed version of this algorithm? Feb 24, 2021 at 16:57
• @RobertHarvey could you explain that a bit further please? Feb 24, 2021 at 16:58

There are some differences between the CART and C4.5 algorithms for building decision trees. For instance, CART uses Gini Impurity to pick features while C.4.5 uses Shannon Entropy. I don't think the differences are relevant for the answer, so I will not differentiate between those.

What makes decision trees faster than you would think is:

1. As others have said, these algorithms are 1-lookahead algorithms. They perform local optimizations. At every branch, they choose the rule which maximizes/minimizes whatever metric they use (Gini or Entropy). This means they might miss rules where using a logical operator such as and would result in a better tree. This means you should be very careful/clever when doing feature engineering. For example, say you are trying to predict how much people drink, you might want to feature engineer things like new_feature = hour > 22 & hour < 4 & (friday_night | saturday_night). Decision trees might miss such rules, or give them less importance than they should.
2. More importantly, the metrics used by decision trees can be computed incrementally. Say that you have a feature $X_1 = \{3,1.5,2.5,2,1\}$. The decision tree does not need to compute the metric for X <= 1, then compute the metric again for X <= 1.5, then again for X <= 2, etc. Gini and Entropy were chosen because they can be computed incrementally. First of all, each feature is sorted, so that you have $X_1 = \{1,1.5,2,2.5,3\}$. Secondly, when you compute X <= 1, you can use the result to easily compute X <= 1.5. It's like doing an average. If you have an average of a sample, $\bar x$, and I give you another value $v$, you can cheaply update your average doing, $\bar x \leftarrow \frac{n\bar x+v}{n+1}$. Gini coefficient is calculated as a fraction of sums, which can be easily incrementally computed for the sample.
3. Decision trees can be parallelized. Each node is composed of two branches which are independent. Therefore, at each branch, you have the opportunity to parallelize the tree creation. Furthermore, the feature selection itself can also be parallelized. This is what makes packages like xgboost so fast. Gradient boosting is sequential and cannot be parallelized, but the trees themselves can.