machine learning - What is the computational complexity of constructing and performing a regression tree?

Question

What is the computational complexity of constructing and performing a regression tree? Is there any analysis or conclusion on it?

Thanks!

Answer 1

You can look at the xgboost paper.

The most time consuming part of the tree learning algorithm is getting the data in sorted order. This makes the time complexity of learning each tree O(n log n).