The computational complexity of the PDP estimation with uncertainty is \(\mathcal {O}\left(G \cdot n\right) \cdot \mathcal {O}(\hat{c})\) , with \(\mathcal {O}(\hat{c})\)  being the runtime complexity of single surrogate prediction, \(n\)  denoting the size of the dataset to compute the Monte Carlo estimate and \(G\)  being the number of grid points. In the context of HPO, the general assumption is that the evaluation time of \(\hat{c}\)  is negligibly low as compared to evaluation \(c\) . So we argue that the runtime complexity of computing a PDP with uncertainty estimate can be neglected in this context. When computing ICE curves and their variance estimates beforehand, the algorithmic complexity of Algorithm REF  corresponds to the algorithmic complexity of the tree splitting [1]}.
