# Optimal Prefix Free Codes with Partial Sorting +
## 3 Analysis
### Parameter Alternation \(\alpha(W)\)  
We suggested in Section 2.1 that the number \(|\mathcal{S}|_{EI}\) of blocks of consecutive \(E\)s in the EI signature of an instance can be used to measure its difficulty. Indeed, some \"easy\" instances have few such blocks, and the instance used to prove the \(\Omega(n\log n)\) lower bound on the computational complexity of optimal prefix free codes in the algebraic decision tree computational model in the worst case over instances of size \(n\) has \(n-1\) such blocks (the maximum possible in an instance of size \(n\)). We formally define this measure as the \"alternation\" of the instance (it measures how many times the algorithm suggested by [PERSON] [1] or the [PERSON] algorithm [14] \"alternates\" from an external node to an internal node in its iterative selection process for nodes of minimum weight) and denote it by the parameter \(\alpha\):  
**Definition 3** (Alternation).: _Given an instance of the optimal binary prefix free code problem formed by \(n\) positive weights \(W[1..n]\), its alternation \(\alpha(W)\in[1..n-1]\) is the number of occurrences of the substring \"E1\" in its EI signature \(\mathcal{S}(W)\)._  
In other words, the alternation \(\alpha(W)\in[1..n-1]\) of \(W\) is the number of times that the algorithm suggested by [PERSON] [1] or the [PERSON]'s algorithm [14] selects an internal node immediately after selecting an internal node.  
Note that counting the number of blocks of consecutive \(E\)s is equivalent to counting the number of blocks of consecutive \(I\)s: they are the same, because the EI signature starts with two \(E\)s and finishes with an \(I\), and each new \(I\)-block ends an \(E\)-block and vice-versa. Also, the choice between measuring the number of occurrences of \"E1\" or the number of occurrence of \"1E\" is arbitrary, as they are within a term of 1 of each other (see Section 3.1): counting the number of occurrences of \"E1\" just gives a nicer range of \([1..n-1]\) (as opposed to \([0..n-2]\)). This number is of particular interest as it measures the number of iteration of the main loop in the GDM algorithm:  
**Lemma 4**.: _Given an instance of the optimal prefix free code problem of alternation \(\alpha\), the GDM algorithm performs \(\alpha\) iterations of its main loop._  
Proof.: This is a direct consequence of the definition of the alternation \(\alpha\) on one hand, and of the definition of the algorithm GDM on the other hand.  
The main loop consists in three phases, respectively named grouping, docking, and mixing. The grouping phase corresponds to the detection and grouping of the weights smaller than the smallest internal node: this corresponds to a run of consecutive \(E\) in the EI signature of the instance. The docking phase corresponds to the pairing of the consecutive positions of those weights into internal nodes, and of those internal nodes though produced, recursively until the weight of at least one such internal node becomes equal or larger than the smallest remaining weight: this corresponds to a run of consecutive \(I\) in the EI signature of the instance. The mixing phase corresponds to the ranking of the smallest unpaired weight among the weights of the available internal nodes: this corresponds to an occurrence of \(IE\) in the EI signature of the instance.  
As the iterations of the main loop of the GDM algorithm are in bijection with the runs of consecutive \(E\) in the EI signature of the instance, the number of such iteration is the number \(\alpha\) of such runs.  
In the next section, we refine this result to the number of data structure operations and algebraic operations performed by the GDM algorithm.