<p>In the algebraic decision tree, the result is clear: Elmasry and Belal (<a href="http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1614073" rel="nofollow">Verification Of Minimum Redundancy Prefix Codes</a>)'s lower bound shows that the worst case complexity of computing an optimal prefix free code over all possible sequences of $\sigma$ frequencies is $\Theta(\sigma\lg\sigma)$.</p>

<p>In the $\Omega(\lg \sigma)$-word RAM model, combining Van Leeuwen's reduction to sorting (<a href="http://www.pubzone.org/dblp/conf/icalp/Leeuwen76" rel="nofollow">On The Construction Of Huffman Trees</a>) with any $O(\sigma\lg\lg\sigma)$ sorting algorithm in the RAM model yields an upper bound of $O(\sigma(1+\lg\lg\sigma))$, which many people seem to assume to be optimal, probably by analogy with the situation in the algebraic decision tree model. But the only lower bound available is $\Omega(\sigma)$, the cost of reading the frequencies, leaving a gap between the two bounds.</p>

<p><strong>What is the best upper bound known on the asymptotic complexity of computing an optimal prefix free code in the word RAM model?</strong> Is it $\Theta(\sigma\lg\lg\sigma)$ or $\Theta(\sigma)$? Or somewhere in between?</p>

CC BY-SA 3.0
2012-04-22T16:20:30.580Z
The private BibTeX citation keys are not helpful.  Please add human-readable citations, preferably with links to electronic copies.
Jeffε
CC BY-SA 3.0
2012-04-23T00:54:03.097Z
Heya Jeff: I did try to make the bibtex aliases human readable, following the format Year-Venue-Title-Authors. I added two links now, but the first paper is behind a paywall and the second one is too old to be available digitally: you might have to go down to the library physically...
J.y B.y
<ds.algorithms><sorting><prefix-free-code>
What is the best upper bound known for the complexity of computing an optimal prefix free code in the RAM model?
J.y B.y
# What is the best upper bound known for the complexity of computing an optimal prefix free code in the RAM model?

(Asked by: username_0 on 2012-04-22)

In the algebraic decision tree, the result is clear: Elmasry and Belal ([Verification Of Minimum Redundancy Prefix Codes](http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1614073))'s lower bound shows that the worst case complexity of computing an optimal prefix free code over all possible sequences of $\sigma$ frequencies is $\Theta(\sigma\lg\sigma)$.

In the $\Omega(\lg \sigma)$-word RAM model, combining Van Leeuwen's reduction to sorting ([On The Construction Of Huffman Trees](http://www.pubzone.org/dblp/conf/icalp/Leeuwen76)) with any $O(\sigma\lg\lg\sigma)$ sorting algorithm in the RAM model yields an upper bound of $O(\sigma(1+\lg\lg\sigma))$, which many people seem to assume to be optimal, probably by analogy with the situation in the algebraic decision tree model. But the only lower bound available is $\Omega(\sigma)$, the cost of reading the frequencies, leaving a gap between the two bounds.

**What is the best upper bound known on the asymptotic complexity of computing an optimal prefix free code in the word RAM model?** Is it $\Theta(\sigma\lg\lg\sigma)$ or $\Theta(\sigma)$? Or somewhere in between?

**Tags:** ds.algorithms, sorting, prefix-free-code

> **Comments:**
> **username_1**: The private BibTeX citation keys are not helpful.  Please add human-readable citations, preferably with links to electronic copies.  
> **username_0**: Heya Jeff: I did try to make the bibtex aliases human readable, following the format Year-Venue-Title-Authors. I added two links now, but the first paper is behind a paywall and the second one is too old to be available digitally: you might have to go down to the library physically...  

---

## 0 answers

