# Lexographic Unranking of Combinations Revisited
## 4 Improving Efficiency and Realistic Complexity Analysis
### Realistic Complexity Analysis  
We now propose a more precise complexity analysis based on a more realistic cost model. Recall that we are dealing with big integers. More precisely for \(n\) and \(k\) being given, the ranks as well as the binomial coefficients computed during the generation can have up to \(L_{n,k}=1+\log_{2}\binom{n}{k}\) bits. Using [PERSON]'s approximation, we get that  
\[L_{n,k}\underset{\begin{subarray}{c}\eta\rightarrow\infty\\ k=n\end{subarray}}{\sim}n\left(\alpha\log_{2}\frac{1}{\alpha}+(1-\alpha)\log_{ 2}\frac{1}{1-\alpha}\right).\]  
Besides, the cost of the multiplication of a big integer with \(O(n)\) bits with a smaller integer of \(O(\ln n)\) bits can be bounded by \(O(\frac{n}{\ln n}M(\ln n))\) where \(M(x)\) is the cost of multiplying two \(x\)-bits integers. This can be achieved by writing the big integer in base \(2^{\log_{2}n}=n\) and performing the multiplication using the naive \"textbook\" algorithm in this base. The  
Figure 3: Time (in ms) for unranking a combination, with \(n=10{,}000\) and \(k=25\dots 9975\).  
first term \(\frac{n}{\min n}\) counts the number of operations done in base \(n\) and the second term \(M(\ln)\) is the cost of one single multiplication in this base.  
A rough upper bound for \(M(x)\) is \(x^{2}\), obtained by using the naive multiplication algorithm. Actually, the naive algorithm is often used in practice for small values of \(x\) since the asymptotically more efficient algorithms only become better above a given threshold. For our use-case, \(n\) is likely to fit in a machine word in practice and thus the naive algorithm must be used. Hence, the upper bound of \(O(n\ln n)\) for the cost of the multiplication of a small integer by a big integer should faithfully reflect the actual runtime of our implementations, although it is theoretically not optimal. A tighter bound of \(O(n(\ln\ln n)(\ln\ln\ln n))\) can be obtained by using the Schonhage-Strassen algorithm, although it is not advisable in practice.  
In addition to the cost of the multiplications discussed above, a linear number of comparisons and additions are performed. The cost of one such operation is linear in \(n\) and thus negligible compared to the cost of the multiplications. Finally, the first binomial coefficient must be computed from scratch which can be done at negligible cost compared to \(\frac{n^{2}}{\ln n}M(\ln n)\).  
By combining the above discussion with the results from the previous sections, we get the average bit-complexity of all algorithms when \(k\) grows linearly with \(n\), as presented in Theorem 3.2.  
For all the optimized algorithms of the present paper, there exist a constant \(c>0\) such that for all \(n\) large enough and \(k=\alpha n\) for \(0<\alpha<n\), the bit-complexity of the algorithm is bounded by:  
\[c\cdot n^{2}\ln n\cdot\left(\alpha\log_{2}\frac{1}{\alpha}+(1-\alpha)\log_{2} \frac{1}{1-\alpha}\right).\]  
In Figure 4, we display the time complexity of our algorithm (in green) with the graph of the function \(\alpha\mapsto C\cdot\left(\alpha\ln\frac{1}{\alpha}+(1-\alpha)\ln\frac{1}{1- \alpha}\right)\) where the constant \(C\) was chosen so that the maximum values of both curves coincide.  
This validates experimentally our complexity results. Besides, we checked by profiling the optimized algorithms that most of the run time is spent in the arithmetic operations, which also confirms the validity of our complexity model.