Homework due and quiz #2 – Wednesday, February 17

Posted on February 10, 2016 by Kate Poirier

Section 3.2 #2, 8, 10, 16, and the following:

(1) Assume that n < 2^n whenever n is a positive integer. Use this to show that \log(n) is O(n).

(2) Show that n! is O(n^n).

(3) Determine whether f(x)=x^2 is O(x) or is not O(x).

(4) One algorithm for solving a problem uses n log(n) steps. Another algorithm for solving the same problem uses n^{\frac{3}{2}}. Which algorithm would be better for a large number of inputs n?

Keep in mind that by “\log(n)” here, we mean the logarithm with base 2.

For hints, consult examples 1-9 in section 3.2.

This entry was posted in Homework, Quizzes. Bookmark the permalink.

2 Responses to Homework due and quiz #2 – Wednesday, February 17

  1. ChrisG says:
    February 12, 2016 at 4:13 pm

    I would like to confirm the homework for Wednesday is the book problems plus the 4 problems written down as well?

    Reply

Leave a Reply

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