How to prove $2^{\sqrt{f(n)}} \in O\ (2^{f(n)})$ if $f:\Bbb{N}\rightarrow \Bbb{R^+}$?

Question

How to prove $2^{\sqrt{f(n)}} \in O\ (2^{f(n)})$ if $f:\Bbb{N}\rightarrow \Bbb{R^+}$?

So we want to prove $\exists c\in\Bbb{R^+}:\ [\exists B\in\Bbb{N}:[\ \forall n\in\Bbb{N}:\ n\ge B\rightarrow 2^{\sqrt{f(n)}} \le c(2^{f(n)}))]]$

But we don't know what the function does, so how are we supposed to make the connection, i.e. $2^{\sqrt{f(n)}} \ge g(n)\ge c(2^{f(n)}))$?

Answer 1

Hint: $f(n)+1 \ge \sqrt{f(n)}$ no matter what $f(n)$ is.