title: I need help proving that if f(n) = O(g(n)) implies 2^(f(n)) = O(2^g(n)))
body: <p>In a previous problem, I showed (hopefully correctly) that <code>f(n) = O(g(n))</code> implies <code>lg(f(n)) = O(lg(g(n)))</code> with sufficient conditions (e.g., <code>lg(g(n)) &gt;= 1, f(n) &gt;= 1</code>, and sufficiently large n). </p>
  
  <p>Now, I need to prove OR disprove that <code>f(n) = O(g(n))</code> implies <code>2^(f(n)) = O(2^g(n)))</code>. Intuitively, this makes sense, so I figured I could prove it with help from the previous theorem. I noticed that <code>f(n)</code> can be rewritten as <code>lg(2^f(n))</code> and that <code>g(n)</code> is just <code>lg(2^g(n))</code>, which got me excited...this is taking the log base 2 of both sides of what I want to prove, and it simplifies things a lot! </p>
  
  <p>But I'm pretty sure this won't work. Just because <code>lg(2^f(n)) = O(lg(2^g(n)))</code> does not necessarily mean that <code>2^f(n) = O(2^g(n))</code>...that's backwards from the previous theorem (which said "implies", not "if and only if"). </p>
  
  <p>Do I need to try this proof another way, or can I actually go off of what I have (at least as a starter)? </p>
  
  <p>**Speaking of other ways, maybe I could just argue about how raising 2 to some <code>g(n)</code> that is "above" an <code>f(n)</code> will still keep it higher? It almost feels like a common sense argument, but maybe I'm missing something important..</p>
  
  <p>**Oh, oops! I forgot to add that <code>f(n)</code> and <code>g(n)</code> are asymptotically positive. By our textbook definition, this means that they are "positive for all sufficiently large n." </p>