3
$\begingroup$

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?

2 Answers 2

2

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$.

  • 0
    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$.2012-09-15
5

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?

  • 0
    Unfortunately I don't have enough points to upvote yet but thanks a lot for your help.2012-09-15