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

Leave a Reply

Your email address will not be published. Required fields are marked *