Test #1 Review – Christian Guerrero

Posted on March 3, 2016 by ChrisG

Section 3.2 Number 19

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

2 Responses to Test #1 Review – Christian Guerrero

Kate Poirier says:

March 7, 2016 at 2:36 pm

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

Reply
- Kate Poirier says:
  
  March 7, 2016 at 2:53 pm
  
  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)$ .
  
  Reply

Leave a Reply to Kate Poirier Cancel reply

The OpenLab at City Tech:A place to learn, work, and share

The OpenLab is an open-source, digital platform designed to support teaching and learning at City Tech (New York City College of Technology), and to promote student and faculty engagement in the intellectual and social life of the college community.

top

The OpenLab at City Tech:A place to learn, work, and share

The OpenLab is an open-source, digital platform designed to support teaching and learning at City Tech (New York City College of Technology), and to promote student and faculty engagement in the intellectual and social life of the college community.