# Optimal Prefix Free Codes with Partial Sorting +
## 3 Analysis
### Running Time Upper Bound  
In order to measure the number of queries performed by the GDM algorithm, we detail how many queries are performed in each phase of the algorithm. * The initialization corresponds to a constant number of data structure operations: a select operation to find the third smallest weight (and separate it from the two smallest ones), and a simple partialSum operation to sum the two smallest weights of the input. * Each grouping phase corresponds to a constant number of data structure operations: a partialSum operation to compute the weight of the smallest internal node if needed, and a rank operation to identify the unpaired weights which are smaller or equal to that of this node. * The number of operations performed by each docking and mixing phase is better analyzed together: if there are \(i\) \"1\" in the \(I\)-block corresponding to this phase in the EI signature, and if the internal nodes are grouped on \(h\) levels before generating an internal node of weight larger than the smallest unpaired weight, the docking phase corresponds to at most \(h\) partialSum operations, whereas the mixing phase corresponds to at most \(\log_{2}(i/2^{h})\) partialSum operations, which develops to \(\log_{2}(i)-h\), for a total of \(h+\log_{2}(i)-h=\log_{2}i\) data structure operations. * The conclusion phase corresponds to a number of data structure operations logarithmic in the size of the last block of _Is_ in the EI signature of the instance: in the worst case, the weight of one pure internal node is computed for each batch, through one single partialSum operation each time. Lemma 4 and the concavity of the logarithm function yields the total number of data structure operations performed by the GDM algorithm:  
Lemma 5: _Given an instance of the optimal binary prefix free code problem of alternation \(\alpha\), the GDM algorithm performs within \(O(\alpha(1+\log\frac{n-1}{\alpha}))\) data structure operations on the deferred data structure given as input._  
Proof. : For \(i\in[1..\alpha]\), let \(n_{i}\) be the number of internal nodes at the beginning of the \(i\)-th docking phase. According to Lemma 4 and the analysis of the number of data structure operations performed in each phase, the GDM algorithm performs in total within \(O(\alpha+\sum_{i=1}^{\alpha}\log n_{i})\) data structure operations. Since there are at most \(n-1\) internal nodes and the sum \(\sum_{i=1}^{\alpha}n_{i}\leq n-1\), by concavity of the logarithm the number of queries is within \(O(\alpha+\alpha\log\frac{n-1}{\alpha})=O(\alpha(1+\log\frac{n-1}{\alpha}))\). Combining this result with the complexity of the partialSum deferred data structure from Lemma 2 directly yields the complexity of the GDM algorithm in algebraic operation (and running time):  
Lemma 6: _Given an instance of the optimal binary prefix free code problem of alternation \(\alpha\), the GDM algorithm runs in time within \(O(n(1+\log\alpha)+\alpha(\log n)(1+\log\frac{n-1}{\alpha}))\), all within the algebraic decision tree computational model._  
Proof. : Let \(q\) be the number of queries performed by the GDM algorithm. Lemma 5 implies that \(q\in O(\alpha(1+\log\frac{n-1}{\alpha}))\). Plunging this into the expression \(O(n(1+\log q)+q\log n)\) from Lemma 2 yields a complexity within \(O(n(1+\log\alpha)+\alpha(\log n)(1+\log\frac{n-1}{\alpha}))\). Some simple functional analysis further simplifies the expression to our final upper bound:  
Lemma 7: _Given two positive integers \(n>0\) and \(\alpha\in[1..n-1]\),_  
\[O\left(\alpha(\log n)(\log\frac{n}{\alpha})\right)\subseteq O\left(n(1+\log \alpha)\right)\]  
Proof. : Given two positive integers \(n>0\) and \(\alpha\in[1..n-1]\), \(\alpha<\frac{n}{\log n}\) and \(\frac{\alpha}{\log\alpha}<n\). A simple rewriting yields \(\frac{\alpha}{\log\alpha}<\frac{n}{\log^{2}n}\) and \(\alpha\log^{2}n>n\log\alpha\). Then, \(n/\alpha<n\) implies \(\alpha\times\log n\times\log\frac{n}{\alpha}<n\log\alpha\), which yields the result.