## 5 Experimental Results
### Time Complexity  
In this section, we analyze the time complexity of the studied algorithms. The proposed algorithms differ from _NSGA-II_ only in the sorting method used when selecting the best elements for the next generation. In addition, this is the most computationally expensive part. The execution times of the other parts of the algorithm are proportional to the population size. That is why we report the duration of the sorting procedure for the studied algo  
Figure 10: Average percentage of solutions dominated by other algorithms. The legend is shared among plots.  
rithms in Figure 11. This figure shows the results for 10 knapsacks and random selection. The general trends and relations are similar for all other configurations.  
**Cumulative sorting duration.** Figure 11a shows cumulative sorting duration as a function of the number of generations. As the size of the population remains the same for every generation, cumulative sorting duration increases linearly for all algorithms except _PO-prob_*. This algorithm is a combination of _PO-prob_ for generations 0-350 and _NSGA-II_ afterwards. That is why for _PO-prob_* we observe a curve with two linear pieces with corresponding inclinations.  
We can also observe that _NSGA-II_ and _PO-count_ require similar time for sorting, and _NSGA-III_ performs the sorting procedure slightly faster. Contrarily, time complexity of _PO-prob_ and _PO-prob_* is significantly less. Indeed, _PO-prob_ does not perform pairwise comparison of elements in the current population. Instead the values are compared separately for every objective and are afterwards multiplied to obtain approximate ranking.  
These experimental results confirm theoretical expectations based on the definition of the proposed algorithm.  
**Sorting duration as a function of _pop_size.** In Figure 11b, we report the dependency of sorting time on the population size for values of _pop_size_ ranging from 50 to 500. The reported values are averages of 100 independent executions of one iteration of the corresponding genetic algorithm. We do not show the results for _PO-prob_* here, as it is an aggregation of two other algorithms.  
From the figure, we can see that _PO-prob_ requires much less time than all other algorithms. The results for _NSGA-II_ and _PO-count_ tend to be very close, as in other experiments. Finally, _NSGA-III_ is in between.  
This observation also has a theoretical explanation. Indeed, choosing the next generation for _NSGA-III_ and _NSGA-II_ has time complexity of \(max\{O(N^{2}M),O(N^{2}l\phi_{M-2}N)\}\)  
Figure 11: Time complexity for random selection and 10 knapsacks, \(n_{k}=10\). (**a**) Cumulative sorting duration as a function of number of generations; (**b**) Sorting duration as a function of population size, _pop_size._  
and \(O(N^{2}M)\) respectively, where \(M\) stands for the number of objectives and \(N\) is the population size, see [6; 16]. At the same time, sorting in _PO-prob_ comes down to independent sorting procedures with respect to every objective. The time complexity of this procedure is \(O(NMlog(N))\).  
All these results prove the computational efficiency of the approximate ranking calculation procedure used in _PO-prob_ both theoretically and via the experiments.