Editing Elias omega coding (section)

== Code length ==
For the encoding of a positive integer {{math|''N''}}, the number of bits needed, {{math|''B''(''N'')}}, is recursively:<math display="block">
\begin{align}B(0) & = 0\,, \\
B(N) & = 1 + \lfloor \log_2(N) \rfloor + B(\lfloor \log_2(N) \rfloor)\,.
\end{align}</math>That is, the length of the Elias omega code for the integer <math>N</math> is<math display="block">1 + (1 + \lfloor \log_2 N \rfloor{}) + (1 + \lfloor \log_2  \lfloor \log_2 N \rfloor{} \rfloor{}) + \cdots </math>where the number of terms in the sum is bounded above by the [[Iterated logarithm|binary iterated logarithm]].
To be precise, let <math>f(x) = \lfloor \log_2 x \rfloor{} </math>. We have <math>N > f(N) > f(f(N)) > \cdots > f^k(N) = 1 </math> for some <math>k </math>, and the length of the code is <math>(k+1) + f(N) + f^2(N) + \dots + f^k(N) </math>. Since <math>f(x) \leq \log_2 x </math>, we have <math>k \leq \log_2^*(N)  </math>.

Since the iterated logarithm grows slower than all <math>\log_2^n N  </math> for any fixed <math>n</math>, the asymptotic growth rate is <math>\Theta(\log_2 N + \log_2^2 N + \cdots) </math>, where the sum terminates when it drops below one.

=== Asymptotic optimality ===
Elias omega coding is an asymptotically optimal prefix code.<ref>{{Cite journal |last=Elias |first=P. |date=March 1975 |title=Universal codeword sets and representations of the integers |url=https://ieeexplore.ieee.org/document/1055349 |journal=IEEE Transactions on Information Theory |language=en |volume=21 |issue=2 |pages=194–203 |doi=10.1109/TIT.1975.1055349 |issn=0018-9448|url-access=subscription }}</ref>

'''Proof sketch.''' A prefix code must satisfy the [[Kraft–McMillan inequality|Kraft inequality]]. For the Elias omega coding, the Kraft inequality states<math display="block">\sum_{n=1}^\infty \frac{1}{2^{O(1) + \log_2 n + \log_2\log_2 n + \cdots}} \leq 1 </math>Now, the summation is asymptotically the same as an integral, giving us<math display="block">\int_1^\infty \frac{dx}{x \times \ln x \times \ln \ln x \cdots} \leq O(1)  </math>If the denominator terminates at some point <math>\ln^k x</math>, then the integral diverges as <math>\ln^{k+1} \infty</math>. However, if the denominator terminates at some point <math>(\ln^k x)^{1+\epsilon}</math>, then the integral converges as <math>\frac{1}{(\ln^{k} \infty)^\epsilon} </math>. The Elias omega code is on the edge between diverging and converging.