# Lexographic Unranking of Combinations Revisited
## 4 Improving Efficiency and Realistic Complexity Analysis
### Improving the Implementations of the Algorithms
```
1:functionOptimizedUnranking-Recursive\((n,k,u)\)\(L\leftarrow[0,\ldots,0]\)\(\triangleright\)\(k\)components
2:\(L\leftarrow[0,\ldots,0]\)\(\triangleright\)\(k\)components
3:\(b\leftarrow\texttt{binomial}(n,k)\)
4:\(\texttt{UnrankTR}(L,0,0,n,k,u,b)\)
5:return\(L\)
```
**Algorithm 6** Unranking a combination with optimization. We propose a second time efficiency comparison for some algorithms with their optimizations in Figure 2. Comparing this plot with the leftmost one of Figure 1, we note that, when \(n=10{,}000\), the algorithms run approximately 45 times faster. Again, we note that Algorithm 5 is still less efficient than the others, which all seem to be equivalent. Figure 2: Time (in ms) for unranking a combination with the optimized algorithms. To understand the behavior of the curves of the above plot, we introduce another way to analyze the time complexity in Figure 3. Now, we take \(n=10{,}000\) and we let \(k\) range from 250 to 9750 with an iteration step of 250. For each step, we present an average value for 500 tests. Again (in the leftmost plot), the dashed lines correspond to the first version of each algorithm and the solid lines to the optimized versions. In the rightmost plot, we only focus on the optimized versions of the four algorithms. We remark that the worst time complexity is obtained when \(k=n/2\). In addition, Algorithm 6 and the tail-recursive Algorithms 4 and 7 behave in almost the same way. Whereas Algorithm 4 is a little bit more efficient when \(k<n/2\), the two other are a bit more efficient for the second half range. Thus, the curves for Algorithms 4, 6, and 7 (once optimized) are hard to distinguish. There is a surprising explanation for this. In fact, it can be shown that all three algorithms perform the exact same arithmetic operations on big integers except for a few terms at then end of their execution, due to their different base cases. In the case of the recursive and factoradic-based algorithms, the similarity goes further. Algorithm 7, being tail-recursive, it can be automatically translated into the imperative style (the conversion of a tail-recursive algorithm into its imperative version is called \"tail-call\" optimization and is implemented by most compilers for languages with recursion) and the result of the automatic translation is an algorithm which is almost identical to Algorithm 2. In the case of Algorithm 4 (once optimized), although the computations are the same, they are used to obtain the values of the \(c_{i}\) coefficients in a different order, which makes the parallel less obvious. As a result, the only fundamental differences between all these algorithms are their base cases. Since they are all based on a different combinatorial point of view, their base cases have been characterized slightly differently, but, as we can see by comparing the results of their complexity analyses (establishing how many calls to binomial are done), this only impacts the second order of their complexity. Besides, for all algorithms, a significant speed-up can be achieved by re-using the value of the most recently computed binomial coefficient.