**Time and Space complexity for Training:**

In the training stage for features (dimensions) in the dataset, we sort the data which takes **O(n log n)** time following which we traverse the data points to find the right threshold which takes **O(n)** time. Subsequently, for d dimensions, the total time complexity would be:

Usually while training a decision tree we identify the nodes which are typically stored in the form of if-else statements due to which training space complexity is **O(nodes)** .

**Time and Space Complexity for Testing:**

Moreover, the testing time complexity is **O(depth)** as we have to traverse from the root to a leaf node of the decision tree i.e., testing space complexity is **O(nodes)** .