takes $O(dm+dn')$ time to evaluate $S_{01}(x_j)$ and $S_{10}(x_j)$, $\forall 1\le j\le m$, at all the possible partition locations of $R_1$. Therefore, it takes $O(d^2+md+n'd)$ time to compute surface area for all the possible partition locations and class label assignments. Similarly, the costs of computing volume for all possible partition locations is $O(n'd)$. Thus for all the possible partition locations and class label assignments at $R_1$, the total cost of computing SVR is $O(d^2+md+n'd)$.

#### Time Complexity of Algorithm 1

Before working on any partitions, we first need to sort the whole dataset for all features, taking $O(dn\log n)$ time. For a node with $n'$ samples and $m$ leaf nodes in the current tree, there are $dn'$ possible partition locations. It takes $O(dn')$ time to compute signed impurity for all possible class label assignments and all partition locations; $O(d^2+md+n'd)$ time to compute surface-to-volume ratio for all possible class label assignments and all partition locations; $O(dn')$ time to find the best partition when all the signed impurities and SVR are already computed. The overall time complexity of finding the best partition at this node is $O(d^2+md+n'd)$. Let $a_n$ be the number of leaf nodes of the tree output by Algorithm 1, with 