How to set this big O statement to get the results in the article?

Question

In this article: https://arxiv.org/pdf/1603.05346v2.pdf, in page 3, when setting the K they suggested, I did not managed to get their results. This is the point: What I did in the meantime: What to do next?

Answer 1

Assuming $\varepsilon$ and $C$ are fixed positive constants and $n$ is positive and let $x := \varepsilon n$, then by applying L'Hospital's rule twice, we can show the first statement: $$ \lim_{x \rightarrow \infty} n \log{(n / k)} /k = \lim_{x \rightarrow \infty} \frac{\log{\frac{x}{C \log{x}}} }{\frac{C \log{x}}{x}} = \lim_{x \rightarrow \infty} \frac{\frac{C \log{x}}{x} \frac{C \log{x} - C}{ \left( C \log{x}\right)^2}}{\frac{C - C \log{x}}{x^2}} = \lim_{x \rightarrow \infty} \frac{x}{-C \log{x}} = -\frac{1}{C} \lim_{x \rightarrow \infty} x $$ Therefore, asymptotically, $n \log{(n / k)} /k = O(x) = O(\varepsilon n)$.

Similarly, to show the second statement on the space usage, we can again apply L'Hospital's rule: $$ \lim_{x \rightarrow \infty} \frac{x}{C \log{x}} = \lim_{x \rightarrow \infty} \frac{1}{C/x} = \frac{1}{C}\lim_{x \rightarrow \infty} x $$ Therefore, asymptotically, we get that: $$ k \log{(n / k)} = \frac{C}{\varepsilon} \log{(x)} \log{ \left( \frac{x}{C \log{x}} \right)} \leq \frac{C}{\varepsilon} \log{(x)} \log{(x)} = O\left( (1 / \varepsilon) \log^{2}{(\varepsilon n)}\right) $$

Additional Explanation. To simplify the limit $x \rightarrow c$ of the quotient of two functions $f(x)/g(x)$, that have the same type of singularity at $c$, we can just differentiate the numerator and denominator \begin{equation} \lim_{x \rightarrow c} \frac{f(x)}{g(x)} = \lim_{x \rightarrow c} \frac{f'(x)}{g'(x)} \tag{1} \end{equation} which often simplifies the quotient and converts the limit to a simpler limit that we can evaluate directly. This rule in Eq. (1) is called L'Hôpital's rule. You can find more explanation in Wikipedia article: https://en.wikipedia.org/wiki/L%27H%C3%B4pital%27s_rule