# Test #1 Review – Christian Guerrero

Section 3.2 Number 19

This entry was posted in Test #1 Review. Bookmark the permalink.

### 2 Responses to Test #1 Review – Christian Guerrero

1. Kate Poirier says:

Hi Christian, this looks pretty good! I have a comment about the first part, where you’re showing that $f(n) = 2^{n+1}$ is $O(2^n)$. You have a statement that reads, “$2^{n+1} \leq 2^n$.” This statement as written is false. All is not lost, though, because I don’t think it was the statement you intended to write. Here’s a suggestion for a possible change: “Since $2^{n+1} = 2\cdot 2^n$, we have that $2^{n+1} \leq 2\cdot 2^n$ for all values of $n$. Since $2^{n+1} \geq 0$, this implies that $|2^{n+1}| \leq 2 |2^n|$ for all values of $n$. Therefore, $f(n) = 2^{n+1}$ is $O(2^n)$ with witnesses $(C,k) = (2,1)$.” (Note that setting $k =1$ here is a choice…we could have chosen any positive value for k.)

• Kate Poirier says:

I also have a comment about your second part! What you’ve written describes an intuitive understanding of what’s going on, but it’s not a formal proof. Here’s one way to prove the statement formally.

We’ll prove that $f(n) = 2^{2n}$ is not $O(2^n)$. This will be a proof by contradiction. This means that we’ll assume that $f(n) = 2^{2n}$ is $O(2^n)$ and try to derive a contradiction. Since $f(n) = 2^{2n}$ is $O(2^n)$ this means that there exists a pair of positive constants $(C,k)$ such that $|2^{2n}| \leq C|2^n|$ for all $n>k$. Since both $2^{2n}$ and $2^n$ are $\geq o$ for all values of $n$, we can remove the absolute value bars, so $2^{2n} \leq C\cdot 2^n$ for all $n>k$. The function $F(n) = \log_2(n)$ is an increasing function, so you can take $\log_2$ of both sides without changing the inequality. This tells us that $2n \leq \log_2(C\cdot 2^n)$ for all $n >k$. The right-hand-side is equal to $\log_2(C) + n$ (using log rules). Therefore, we have that $2n \leq \log_2(C) + n$ for all values of $n>k$. Subtracting $n$ from both sides, this means that $n \leq \log_2(C)$ for all $n>k$. But this is a contradiction! The value $n$ can’t stay below the value $\log_2(C)$ for ALL $n>k$. Therefore, there can exist no pair of positive constants $(C, k)$ so that $|2^{2n}| \leq C|2^n|$ for all $\latex n>k$. This means that $f(n) = 2^{2n}$ is not $O(2^n)$.