What is the computational complexity of training a Decision Tree?

Training a Decision Tree typically takes O(n log n * d) time depending on dataset size and feature count.

At each node, the algorithm evaluates splits across all features and possible thresholds. Sorting features dominates cost, leading to O(n log n) per feature in naive implementations. Optimizations reduce this using presorted values or histograms. Depth of the tree adds additional multiplicative cost.