|
|
|
אורך הקידוד, לכן, הוא
<center><math>hO(1) + h= O(1) =+ \min_k K\{n_k(x) + 1\} += O(1) =+ \left\lceil K\log_{|\Sigma|}\left(\frac{1}{P_U(x)}\right) +\right\rceil O(1).</math></center> \leq
\log_{|\Sigma|}\left(\frac{1}{P_U(x)}\right) + O(1).</math></center>
נשים לב כי,
<center><math>
K(x)
=
\log_{\left| \Sigma \right|}
\left(
\frac{1}{\left| \Sigma \right|^{-K(x)}}
\right)
\leq
\log_{\left| \Sigma \right|}
\left(
\frac{1}{\sum_{i \;|\; M_i(\epsilon) = x} \left| \Sigma \right|^{- \left| \langle M_i \rangle \right|} }
\right)
=
\log_{\left| \Sigma \right|}
\left(
\frac{1}{ P_U(x) }
\right)
,
</math></center>
ולכן
<center><math>
K(x)
\leq
\log_{\left| \Sigma \right|}
\left(
\frac{1}{ P_U(x) }
\right)
+
O(1)
</math></center>
כנדרש.
|
