## 4 Methodology
\begin{split} T_{\text{SAHH}}&=T_{p}+T_{f}+T_{s}+ s_{\text{max}}*(T_{p}+T_{f}+T_{s})\\ &=\mathcal{O}\Big{(}s_{\text{max}}*\text{sup}\Big{\{}T_{p},T_{f},T_{s}\Big{\}}\Big{)}\,,\end{split}  \tag{7}\]

since \(T_{p}\), \(T_{f}\), and \(T_{s}\) are also the computational costs of evaluating the perturbator, objective function, and the selector, respectively; and \(s_{\text{max}}\) is the maximal number of steps carried out in this high-level search. Plus, SAHH is a single-agent algorithm, so selection, perturbation, and acceptance are actions considered to have constant time, i.e., \(T_{\bar{p}}=T_{\bar{s}}=\mathcal{O}(1)\). Otherwise, the objective function at this high level stands for the performance metric described in (5), so its computing cost is given by \(T_{\bar{f}}=\mathcal{O}(N_{r}*T_{\text{uMH}})\), where \(N_{r}\) is the number of repetitions, and \(T_{\text{uMH}}\) is the cost of implementing a candidate uMH. Naturally, the time for calculating the median and interquartile range is disregarded due to its magnitude. In summary, we can rewrite the SAHH time complexity as

\[T_{\text{SAHH}}=\mathcal{O}(N_{r}*s_{\text{max}}*T_{\text{uMH}}). \tag{8}\]

Now, regarding the low level, the time complexity for an unfolded metaheuristic composed of up to \(\varpi_{\text{max}}\) search operators yields

\[T_{\text{uMH}}=\mathcal{O}\big{(}\varpi_{\text{max}}*N*D*T_{p}\big{)}, \tag{9}\]

Figure 9: \(p\)-Values obtained from the pairwise (one-sided) Wilcoxon signed-rank test to the fitness values achieved for each problem of the categories (DU) and by considering different dimensions. Blue dashed stroke stands \(p=0.05\). (**a**) Experiment 1. (**b**) Experiment 2.

since \(N\) is the population size, \(D\) is the dimensionality, and \(T_{p}\) is the computational cost of evaluating the perturbator. According to the well-known Big-\(\mathcal{O}\) definition, this value can be determined such as \(T_{p}=\sup\{T_{p,1},\ldots,T_{p,\varnothing}\}\) for the uMH. It is easy to notice that the initialiser, finaliser, and selectors have an irrelevant complexity contribution. Besides, we focus on analysing the procedure and not the problem to solve, so we can adopt without loss of generality that the time complexity of evaluating the fitness is constant. Equation (9) can be employed to find the theoretical time complexity of any unfolded metaheuristic for some given conditions, for example, Experiments 1 or 2. In that case, we must use the worst case for \(T_{p}\); i.e., \(T_{p}=\mathcal{O}(N^{2})\) for the Genetic Crossover perturbator with Cost-based Roulette Wheel Pairing [47]. Thus, uMHs have a cubic time complexity with respect to the population size and a linear one with respect to the dimensionality, which is relatively high but affordable considering the context of designing solvers. Keeping this in mind, we can express the time complexity of the overall approach \(T_{\text{SAHH}}\) by plugging (9) in (8), as shown,

\[T_{\text{SAHH}}=\mathcal{O}\Big{(}N_{r}*s_{\text{max}}*\alpha_{\text{max}}*D*N ^{3}\Big{)}. \tag{10}\]

This expression gives us information about which components influence the time complexity of the overall approach. Notice that we considered the maximal number of search operators \(\varpi_{\text{max}}\) instead of \(\varpi\), which can be different from one uMH to another. From the above analysis, it is exciting to surmise that the running time scales linearly with the problem dimensionality and cubically with the population size; which is somehow manageable. The main reason is the high-level metaheuristic (i.e., SAHH) controlling the process, which performs one modification per step in a single element of the unfolded metaheuristic. For the scope of this research, SAHH constitutes a good prospect with a low computational burden. Furthermore, we can use (9) to assess the order of operations required by the designed uMHs to tackle problems with different characteristics and dimensionalities.