# Optimal Prefix Free Codes with Partial Sorting +
## 1 Introduction
### Contributions  
We answer in the affirmative for many classes of instances (extending and formalizing the proofs of the same theoretical results previously described in 2016 [21]), identified by the \"alternation\" measure \(\alpha\in[1..n-1]\) assigning a difficulty to each instance (formally defined in Section 3.1):  
Theorem 1: _The computational complexity of optimal binary prefix free code is within \(\Theta(n(1+\log\alpha))\) in the algebraic decision tree computational model, in the worst case over instances of size \(n\) and alternation \(\alpha\)._  
Proof: We describe in Lemma 2 of Section 2.2 a deferred data structure which supports \(q\) queries of type rank, select and partialSum in time within \(O(n(1+\log q)+q\log n)\), all within the algebraic decision tree computational model. We describe in Section 2.3 the Group-Dock-Mix (GDM) algorithm, inspired by the [PERSON]'s algorithm [14], modified to use this deferred data structure to compute optimal prefix free codes given an unsorted input, and we prove its correction in Lemma 3. We show in Lemma 8 that any algorithm \(A\) in the algebraic decision tree computational model performs within \begin{table}
\begin{tabular}{l c c c c l} \hline \hline
**Year** & **Name** & **Time** & **Space** & **Ref.** & **Note** \\ \hline
1952 & [PERSON] & \(O(n\log n)\) & \(O(n)\) & [1] & original \\
1976 & [PERSON] & \(O(n)\) & \(O(n)\) & [14] & sorted input \\
1995 & Moffat and Katajainen & \(O(n)\) & \(O(1)\) & [18] & sorted input \\
1998 & Moffat and Turpin & \(O(r(1+\log(n/r)))\) & “efficient” & [15] & compressed input and Output \\
2001 & Mildiu et al. & \(O(n)\) & \(O(1)\) & [19] & sorted input \\
2006 & Belal and Elmasry & \(O(\log^{2k-1}n)\) & \(O(n)\) & [16] & \(k\) distinct code lengths and sorted input \\
2006 & Belal and Elmasry & potentially \(O(kn)\) & \(O(n)\) & [16] & \(k\) distinct code lengths \\
2005 & Belal and Elmasry & \(O(16^{k}n)\) & \(O(n)\) & [17] & \(k\) distinct code lengths \\
2016 & Group-Dock-Mix & \(O(n(1+\log\alpha))\) & \(O(n)\) & [here] & \(\alpha=|\mathcal{S}|_{E}\in[1..n-1]\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: A selection of results on the computational complexity of optimal prefix free codes. \(n\) is the number of weights in the input; \(r\in[1..n]\) is the number of distinct weights in the input; \(k\in[1..n-1]\) is the number of distinct codelengths produced; and \(\alpha\in[1..n-1]\) is the difficulty measure introduced in this work, the number of alternation between External nodes and Internal nodes in an execution of the algorithm suggested by [PERSON] [1] or by [PERSON]’s algorithm [14] (see Section 3.1 for the formal definition). \(\Omega(n\log\alpha)\) algebraic operations in the worst case over instances of size \(n\) and alternation \(\alpha\). We show in Lemma 5 that the GDM algorithm performs \(q\in O(\alpha(1+\log\frac{n-1}{\alpha}))\) such queries, which yields in Corollary 6 a complexity within \(O(n(1+\log\alpha)+\alpha(\log n)(\log\frac{n}{\alpha}))\), all within the algebraic decision tree computational model. As \(\alpha\in[1..n-1]\) and \(O(\alpha(\log n)(\log\frac{n}{\alpha}))\subseteq O(n(1+\log\alpha))\) for this range (Lemma 7), the asymptotic optimality ensues. When \(\alpha\) is at its maximal (i.e., \(\alpha=n-1\)), this complexity matches the tight asymptotic computational complexity bound of \(\Theta(n\log n)\) for algorithms in the algebraic decision tree computational model in the worst case over all instances of size \(n\). When \(\alpha\) is substantially smaller than \(n\) (e.g., \(\alpha\in O(\log n)\), which practicality we discuss in Section 4), the GDM algorithm performs within \(o(n\log n)\) operations, down to linear in \(n\) for finite values of \(\alpha\). Another natural question is whether practical instances present small enough values of parameters such as \(k\) and \(\alpha\) that taking advantage of them makes a difference.