Computational Complexity for a Binary Tree At the root node, for each of p variables – Sort all values, compute quality for each split – O(pN log N) time for real-valued or ordinal variables Subsequent internal node operations each take O(N' log N') -e.g., balanced tree of depth K requires pN log N + 2(pN/2 log N/2) + 4(pN/4 log N/4) + ….
{}