Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In the question, we are to assume that f(n) is O(g(n)). Next, we have to decide whether 2^f(n) is O(2^g(n)). According, to some solutions on the internet, this can be proven to be false if we take f(n)=2n and g(n)=n. However, I'm not able to completely derive the proof to backup the premise that it is false.

Here's what I have thus far: Suppose we take f(n)=2n and g(n)=n. We know that f(n)≤ C*g(n) for C>0 and ∀ n≥n0≥0. After substituting and raising both sides to base 2, we get: 2^(2n)≤2^(c*n)≡4^n≤2^(c*n)...

Here's where I'm stuck. What I'm trying to do is as follows: for all n0 and C, I'm trying to find an n>=n0 such that 2^f(n) > 2^(c*g(n)). How should I proceed?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

Certainly $2n=O(n)$. To show that $2^{2n}$ is not $O(2^n)$, informally we want to show that in the long run $2^{2n}$ grows much faster than $2^n$. More formally, we need to show that for any $N$, and any fixed constant $c$, there exists $n \gt N$ such that $2^{2n}\gt c2^n$.

For any $N$, choose $n \gt N$ such that $2^n \gt c$. Then $2^{2n}=(2^n)^2\gt c2^n$.

share|improve this answer
    
Great. I just had a question though. Shouldn't we be looking to prove 2^(2n) > 2^(cg(n)) instead of 2^(2n) > c*2^n. I say this because by definition f(n) is O(g(n)). This means that f(n)<=cg(n), thus, shouldn't both sides of this equation be raised to base 2. I don't see why the c should be ignored. –  user600194 Sep 15 '12 at 2:43
    
Here $g(n)=n$. Note for any $c\gt$, $2^{2n}\lt 2^{cn}$! To prove that $2^{2n}$ is not $O(2^n}$, we show that for any $c$, $2^{2n}$ is ultimately $\gt c2^n$. In general, for any $p(n)$ and $q(n)$, to show $p(n)$ is not $O(q(n)$, we need to show that for any $c$, $p(n)$ is $\gt cq(n)$ for arbitrarily large values of $n$. Here $q(n)=2^n$. –  André Nicolas Sep 15 '12 at 2:51

You write:

Suppose we take $f(n)=2n$ and $g(n)=n$. We know that $f(n)\le Cg(n)$ for $C>0$ and $\forall n\ge n_0\ge 0$.

You don’t know this unless you specify $C$ and $n_0$. For example, if you set $C=1$, it’s simply false, no matter what $n_0$ you choose: $2n$ is not less than or equal to $n$.

However, if we set $C=2$ and $n_0=0$, we get a true statement: it is indeed the case that $2n\le2n$ for all $n\ge 0$. The fact that we can find $C$ and $n_0$ making this true is what tells us that $2n$ is $O(n)$.

Now you want to show that $2^{2n}$ is not $O(2^n)$. Suppose that it were; then by definition there would be $C>0$ and $n_0>0$ such that $2^{2n}\le C\cdot2^n$ for all $n\ge n_0$. What does it mean to have $2^{2n}\le C\cdot 2^n$ for all $n\ge n_0$? That would tell us that $\dfrac{2^{2n}}{2^n}\le C$ for all $n\ge n_0$. But $\dfrac{2^{2n}}{2^n}=2^{2n-n}=2^n$, so we’d have constants $C>0$ and $n_0\ge 0$ such that $2^n\le C$ for all $n\ge n_0$. Is that actually possible? What happens to $2^n$ as $n$ increases?

share|improve this answer
    
Unfortunately I don't have enough points to upvote yet but thanks a lot for your help. –  user600194 Sep 15 '12 at 2:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.