Prove that an algorithm taking $f(k)$ steps to complete run in polynomial time, subexponential time or exponential time, $f(k)=e^{\sqrt {\log k}}$

Question

Prove that an algorithm taking $f(k)$ steps to complete run in polynomial time, subexponential time or exponential time, $f(k)=e^{\sqrt {\log k}}$.

My attempt: $e^{\sqrt {\log k}} \leq e^{\log k} \leq e^k$. So assume that $O(e^k)$. Then $g(k)=e^k$. Since the limit of $f(k)/g(k)$ is 0 when $k$ goes to infinity, our assumption is then really true, so the algorithm is finished after $O(e^k)$ steps.

We then know that the algorithm runs in exponential time.

Im I doing it right?

Answer 1

Your work so far is good. However, $f(k)$ is even smaller than exponential time. That is, we can find a smaller function $g$ with $f = O(g)$.

As you noted, we have $f(k) \leq e^{\log(k)}$, but $e^{\log(k)} = k$. So, we should find that $f = O(k)$. Indeed, we find that $$ \lim_{k \to \infty}\frac{f(k)}{k} = \lim_{k \to \infty}\frac{e^{\sqrt{\log k}}}{e^{\log k}} = \lim_{k \to \infty} e^{\sqrt{\log k} - \log k} = e^{-\infty} = 0. $$ So, we find that $f = O(k)$ (and in fact, $f = o(k)$). So, the algorithm is polynomial-time.