# Lexographic Unranking of Combinations Revisited
## 4 Improving Efficiency and Realistic Complexity Analysis
### First Experiments to Visualize the Time Complexity in a Real Context  
In the two next plots in Figure 1, we present the average time needed for the computations of 500 combinations for each pair \((n,k=n/2)\) where \(n\) ranges from 250 to 10,000 with a step size of 250. The choice \(k=n/2\) was made because it corresponds to the worst complexity cases when \(k\) varies from 0 to \(n\). To conduct our experiments, we implemented all algorithms in C using the classical GMP library for big integers arithmetic (the implementation and the exhaustive material used for repeating the experiments are available at [[http://github.com/Kerl13/combination_unranking](http://github.com/Kerl13/combination_unranking)]([http://github.com/Kerl13/combination_unranking](http://github.com/Kerl13/combination_unranking)) (accessed on 15 March 2021)). The experiments were run on a standard laptop PC with an I7-8665U CPU, 32 Gb RAM running Ubuntu Linux 2020. Moreover, except for Table 1, which required running different computer algebra systems and thus the X server, the experiments were run in the console while the X server and other time-consuming services (wifi, sound, etc.) were off. On the leftmost plot, we present the average time for the unranking of a combination for \(n\) ranging from 250 to 10,000 by steps of 250 too. Note that all the curves are merged: all algorithms seem to need almost exactly the same time to unrank a combination. In the rightmost plot, we present a version with memoization (memoization is an optimization technique consisting in storing the results of expensive function calls and returning the cached values when the function is called again with the same arguments; this technique is sometimes called \"tabling\") for the algorithms: we first run a pre-computation step storing all binomial coefficients that will be used. The second step consists in unranking the combinations by using the pre-calculated values for the binomial coefficients. In our plot, we present only the time used for the second step. We remark that the recursive Algorithm 3 is not as efficient as the others. Below, we show that this is due to its recursive nature and that this can be easily avoided. As explained above, Algorithm 5 should be less efficient than Algorithm 4, which is indeed apparent in the plots. Our Algorithms 2 and 4 are the most efficient when used in this setup.  
While the number of evaluations of binomial coefficients is linear in \(n\), it is clear that it is not the case for the time complexity of the algorithms (see the leftmost plot). However,  
Figure 1: Time (in ms) for unranking a combination, with \(n=250\ldots 10\),000 and \(k=n/2\).  
once the binomial coefficients have been pre-computed, running the four algorithms without computing binomial coefficients is closer to a linear function but they still are not really linear.  
While memoizing all binomial coefficients when \(n\) is of order of some hundreds is possible, it is no longer the case when \(n\) is of the order of several thousands (for the experiments in Figure 1, we only computed the necessary binomial coefficients using a lazy approach). Such use cases did not occur when the methods (e.g., [22; 23]) were derived. However, now that big integers are more widely used, it becomes reasonable to unrank combinations of large size and it is thus necessary to take the cost of arithmetic operations into account. The first use of big integers for combination unranking appears to date back to 2004 [27].