Suppose that $n=O(\log_2 m)$. Let $f=O(m)$.
How can we prove that $f=O(2^n)$ as well?
I know that $m=2^{\log_2 m}$, but I can't simply plug $n$ there, because $n$ isn't equal to $\log_2 m$, but $O(\log_2 m)$. Can it be proven without refering to the definition of big $O$ directly? But of course I'll be fine with a proof that uses the definition as well.
What motivated me to ask this was the answer to this question.
It may of course be false as well.
As asked here, this is false.
Note $n=0.5 \log_2 m$ is $O(\log_2 m)$ and $f=m$ is $O(m)$. But $2^n = 2^{0.5\log_2 m} = \sqrt{m}$ and $m$ is not $O(\sqrt{m})$.
Indeed, using the actual meaning of $O$ as commonly used in mathematics there would even be more extreme examples. For instance, $n=\log_2 \log_2 m$ is $O(\log_2 m)$ too or even $n=7$ or any constant is $O(\log_2 m)$, while the conclusion clearly does not hold for those $n$.
However, the intended meaning in the linked post seems different. The $O$, at least for the $n$, is rather meant to signify the actual order (of magnitude), what can be denoted as $\Theta$. Now if $c_1 \log_2 m \le n \le c_2 \log_2 m $ and $f = O(m)$ then one has $ f = O(C^n)$ for some constant $C$.
To see this just note that as $\log_2 m \le c_1^{-1}n$ we have $m \le 2^{c_1^{-1}n} = (2^{c_1^{-1}})^n$.
