0

In a paper about color-coding they estimate the complexity of coloring trials needed to achieve an $\varepsilon$-error for $k\in \mathbb{N}$:

$$ \left\lceil\frac{ln(\varepsilon)}{ln{(1-k!/k^k)}} \right\rceil = |ln(\varepsilon)| \cdot \mathcal{O}(e^k)$$

For me it is clear, why there is the $ln(\varepsilon)$ term, but I do not understand how the $\mathcal{O}(e^k)$ is calculated. I think, one should show, that following holds:

$$ \left| \frac{1}{ln(1-k!/k^k)} \right| \in \mathcal{O}(e^k) $$ A bound $\frac{k!}{k^k} > e^{-k}$ was stated in the paper, so it follow:

$$ \left| \frac{1}{ln(1-k!/k^k)} \right| < \left| \frac{1}{ln(1-e^{-k})} \right| $$

Therefore, the statement can be shown, by proving that:

$$ \left| \frac{1}{ln(1-e^{-k})} \right| \in \mathcal{O}(e^k) $$

But at this point i am stuck. My math knowledge is a little bit rusted unfortunately.

otori
  • 33
  • $e^{-k}$ tends to $0$, so $ln(1-e^{-k})$ is equivalent to $e^{-k}$, thus, by applying the inverse, you get your result. – Oussama Boussif May 12 '17 at 10:38
  • I get that with the inverse. But how is the equivalence between $ln(1-e^{-k})$ and $e^{-k}$ shown? – otori May 12 '17 at 10:45
  • Well, since the limit of $\frac{ln(1-x)}{x}$ is $1$ when $x$ tends to $0$, similarly substitute $x$ for $e^{-k}$ ($e^{-k}$ tends to 0) – Oussama Boussif May 12 '17 at 10:47
  • Thank you very much. I used your comments to formulate an answer to the problem. – otori May 12 '17 at 12:24

1 Answers1

1

This answer is based on Oussama Boussif's comments, so credits go to him.

Lets consider following limit which is calculated by applying the rule of l'Hospital:

$$ \lim_\limits{x \rightarrow 0}\frac{ln(1-x)}{x} = \lim\limits_{x \rightarrow 0}{\frac{\frac{d}{dx}\ln(1-x)}{\frac{d}{dx}x}} = \lim\limits_{x \rightarrow 0}{ \frac{\frac{1}{x-1}}{1} = -1} $$

Since $\lim_\limits{k \rightarrow \infty}{e^{-k}} = 0$ we can substitute $x$ with $e^{-k}$ in the limit stated above.

$$ \lim_\limits{k \rightarrow \infty}\frac{ln(1-e^{-k})}{e^{-k}} = -1$$

This means that $|ln(1-e^{-k})|$ and $|e^{-k}|$ are equivalent for $k \rightarrow \infty$ which implies:

$$ \left|ln(1-e^{-k})\right| \in \mathcal{O}(e^{-k}) \Rightarrow \left|\frac{1}{ln(1-e^{-k})}\right| \in \mathcal{O}(e^{k})$$

otori
  • 33