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.
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})$$