is $O(3^k)$ polynomial for $k\in o(n)$?

Question

For variable $n\in \mathbb{N}$, $O(3^n)$ is certainly an exponential, fix any integer $k\in o(n)$, is the function $O(3^k)$ polynomial ? If not when is it possible for $O(3^k)$ to become polynomial for $k$ depends on $n$.

Answer 1

$k$ has to be $O(\log n)$ for $3^k$ (or any $c^k$) to be $O(n^m)$ for some $m$.

Proof: If $k = O(\log n)$, then $k < a \log n$, so $c^k < c^{a \log n} = e^{a \log c \log n} = (e^{\log n})^{a \log c } = n^{a \log c} $ which is polynomial in $n$.

If $\frac{k}{\log n} \to \infty $, we can similarly show that $c^k$ grows faster than any $n^m$ for fixed $m$.

For example, this happens for $k = n^a$ for any $a > 0$ (such as $k = \sqrt{n}$).