Test #1 Review – Kamil Sachryn

 

 

 

Section 3.2 #9

2016-3-4_14946_1

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

One Response to Test #1 Review – Kamil Sachryn

  1. Kate Poirier says:

    Hi Kamil. This mostly looks very good. I do have two comments, though.

    First, when you’re showing that x^2+4x+17 is O(x^3), you have 3 inequalities that hold when x\geq 2; the right-hand-side of each is 3x^3. When you add up the left sides of these inequalities, you get x^2+4x+17 but when you add up the right side, you get 3 \cdot 3x^3 which is 9x^3. This tells you that for x \geq 2, you have x^2+4x+17 \leq 9x^3. But you have written x^2+4x+17 \leq x^3+x^3+x^3 = 3x^3. Following this through, your value of C should be 9, not 3.

    Next, when you’re showing that x^3 is not O(x^2+4x+17), it looks like you’ve shown that the particular choice (C,k) does not work. This is not enough to show that x^3 is not O(x^2+4x+17). Instead you want to show that there are NO POSSIBLE CHOICES of (C,k) that work. Try setting up a proof by contradiction to see this formally. (BTW I added a comment to Christian’s post that included a proof by contradiction for another set of functions…that might be useful for you to look at.)

Leave a Reply

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