analysis - How to prove complexity of algorithms

I have three different algorithms which I want to prove if they are solvable in polynomial/subexponential/exponential time. The algorithms are $f(k) = e^{\sqrt{\log{k}}}$, $f(k) = k^2 + \frac{e^{(k+(\log{k})^2)}}{k}$ and $f(k) = e^{\sqrt{k}}$. The inputs are $k$ and it takes $f(k)$ basic steps to complete.

---

Solution:

I am not really sure how to do it, but I have given it a try.

In order for it to be solvable in polynomial time it should have $O(k^c)$ for some positive integer $c$ I guess. That is:

$$\lim_{k\to\infty}\frac{e^{\sqrt{\log{k}}}}{k^c}$$

should exist.

I guess I use L'Hospital rule to show this. Then I end up with that:

$$\lim_{k\to\infty}\frac{e^{\sqrt{\log{k}}}}{k^c}=\lim_{k\to\infty}\frac{e^{\sqrt{\log{k}}}}{2k^c\sqrt{\log{k}}}=\lim_{k\to\infty}\frac{e^{\sqrt{\log{k}}}}{2k^c(2c\log{k}+1)}$$

It seems like the denominator grows while the numerator stays the same, so the fraction approaches 0 when k approaches infinity. But is this enough to say that the algorithm is solvable in polynomial time? Have I even proved it?

What is the difference between sub-exponential and exponential? I have watched wikipedia but it didn't make me any smarter.

Also, for the last two algorithms, I think they aren't solvable in polynomial time, so I guess I have to show it somehow.

This is how I interpret it, first you try to prove the algorithm is solvable in polynomial time, if you manage to do it, you are done. If you prove that the limit doesn't exist then you move on to sub-exponential/exponential. Is subexponential a special case of exponential, the other way around or neither? How do you solve these kind of problems?

This is driving me crazy. I really want to understand this but I really don't UNDERSTAND this and my textbook has no solution manual.

Hope someone can help me out. Thanks :)

Answer

Take the log.

$\log(\frac{e^{\sqrt{k}}}{k^c})
=\sqrt{k}-c\log(k)
\to \infty
$
since
$\log(k)
= O(k^{\epsilon})
$
for any $\epsilon > 0$.

$\log(\frac{e^{\sqrt{\log(k)}}}{k^c})
=\sqrt{\log(k)}-c\log(k)
\to -\infty
$
since
$\sqrt{x}-x
\to -\infty
$
for any
$x \to \infty

$.