Cost of Finding the Best Split in a Regression Tree
Problem statement
You are growing a regression (CART) tree. At a node you have $m$ samples and $p$ features, and you want to find the single best split: the feature and threshold that minimize the resulting L2 (sum-of-squared-error) loss of the two children.
- What is the complexity of a brute-force evaluation of all candidate splits at this node?
- Can you do better than re-summing the loss from scratch for every candidate threshold? What complexity does the improved method achieve?
Show hint
Treat the search as nested loops and ask what each loop level contributes to the cost.
Relevant roles: ML Engineer, Applied Scientist, Data Scientist and Research Scientist.