number of leaf nodes be $\bar{a}_n = O(\sqrt{n})$.[^4] The storage complexity is trivial and is the same as usual decision trees, i.e., $O(dn)$. We analyze the time complexity of Algorithm 1 in this section. We first introduce the approach to compute surface-to-volume ratio, then discuss the time complexity of building the tree.

#### Computing SVR

Suppose in some intermediate state of building the SVR Tree, the current tree has $m$ leaf nodes $R_1, R_2, \cdots R_m$. We already know the surface and volume of the current tree. Now we need to perform a partition at node $R_1$, which has $n'$ samples. Suppose we partition at $X[j] = x_j$ and obtain two child nodes. The volume of the tree after this partition can be computed by adding the volume of the minority class child node(s), which takes $O(d)$ time. The major concern lies in the computation of the surface area. If both child nodes are in the majority class or the minority class, the surface after partitioning is the surface that node $R_1$ is labeled as the majority class or the minority class. It takes $O(d^2)$ time to compute the surface of $R_1$, and $O(md)$ time to compute all the overlapping 