\[ \]
Andy, you said …\[Then \ 2^{f(x)} \leq 2^{g(x)}\] \[Therefore \ 2^{f(x)} \ is \ O(2^{g(x)})\] That is wrong. \(2^{f(x)} \leq 2^{g(x)}\) actually implies \(2^{f(x)} \ is \ 2^{O({g(x)})}\)
\[ \]
We need to find at least one scenario where this is false.
\[ \]
Let \(f(x) = log(x^{2})\) and \(g(x) = log(x)\).
Suppose that \(f(x)\) is \(O(g(x))\):
\[f(x) \leq c*g(x)\] \[log(x^{2}) \leq c*log(x)\] \[2log(x) \leq c*log(x)\] \[Witness : (c,k) = (4,3) - Domain \ of \ Witness \ (c > 2) \ and \ (k > 0)\]
\[ \] Suppose that \(2^{f(x)}\) is \(O(2^{g(x)})\): \[2^{log(x^{2})} \leq c*2^{log(x)}\]
General: \(log_2(y) = log_2(y)\) \(\rightarrow\) \(2^{log_2(y)} = y\)
\[x^{2} \leq c*x\]
Answer: Since \(x^{2}\) is exponential there is no value of the constant \(c\) that can make the growth of \(g(x)\) overtake the growth of \(f(x)\). This proves that \(2^{f(x)}\) is not \(O(2^{g(x)})\).