# Which bound is better, a logarithmic or a polynomial with arbitrarily small degree?

I have a randomized approximation algorithm which can be tuned by selecting the randomization probabilities. I found out that:

• For any $\epsilon >0$, there are probabilities for which the approximation factor is $O(n^\epsilon)$.
• There are probabilities for which the approximation factor is $O(\ln n)$ (smaller factor is better).

I know that $O(\ln n)$ is asymptotic smallerer than any $O(n^\epsilon)$ when $\epsilon$ is fixed, but here $\epsilon$ can be made arbitrarily small, so I don't know, which of these two bounds is considered better? Specifically:

A. Theoretically, which of these two bounds should I report in a paper? Is the bound $O(n^\epsilon)$ interesting, or is it considered useless given the logarithmic bound?

B. Practically, if I have to run the algorithm on very-big-data, with no possibility of making tests in advance, which tuning is better?

(Just to get some feeling, I compared $n^{0.1}$ with $\ln n$. It turns out that $n^{0.1}$ is better even for very large $n$ - they become equal at about $n=4 \cdot 10^{15}$)

• Depends on what your narrative is. Asymptotics are everything? The logarithmic bound. Real efficiency is a concern? The polynomial. However, if you can express $\epsilon$ as a function of $n$, say $\epsilon = 1/\ln(n)$ -- that is, make the algorithm adaptive, you can be better asymptotically as well. Other than that, why not report both? – Raphael Apr 22 '15 at 14:09
• In fact, $\log n = O(n^{\epsilon})$ for every $\epsilon > 0$. Even more, $\log n = O(n^{\epsilon})$ for $\epsilon = \log\log n/\log n$. – Yuval Filmus Apr 22 '15 at 14:18
• Another issue is that there are hidden constants – it could be $\ln n$ against $100n^{0.1}$, for example. The constants affect the cutoff. – Yuval Filmus Apr 22 '15 at 14:45
• @Raphael's suggestion made a lot of sense according to what I asked, but on the same time, it seemed too good to be true that I can get a constant factor. So, following Yuval's suggestion, I calculated the constants and found it that the polynomial bound has a $1+1/\epsilon$ constant, which immediately makes it worse than the logarithmic bound, as it should be :) I learned my lesson. – Erel Segal-Halevi Apr 24 '15 at 12:29

Since $\log n = O(n^{\epsilon})$ for an $\epsilon > 0$, if you can prove an approximation ratio of $O(\log n)$, then approximation ratios of $O(n^{\epsilon})$ (for any $\epsilon > 0$) immediately follow. You should always prove the best approximation ratio that you can, unless:
• Prove non-asymptotic guarantees on the approximation ratio, say $100\log n$ and $(2/\epsilon)n^{\epsilon}$. This allows you to obtain concrete guarantees for every $n$.
• Do experiments. The experiments reveal the actual approximation ratio on the average. If you can fit your results to a nice function, you can say that empirically, the average approximation ratio is (say) $10\log n$, though in the worst case all you know is (say) $100\log n$. Experiments, however, are not so welcome in theoretical papers, unfortunately.