CS 127 Assignments

Assignment 2: Computational Complexity

Work through Section 2.8 Self-Check Exercises (1-4) on page 118 of your textbook. See the clarifications / modifications below. You may share ideas with others in the class, but you should turn in your own assignment.

Clarifications / modifications to questions, having learned from past experience:

Question 1: The problem says "Indicate whether the algorithm is O(n) or O(n2)." This is somewhat vague, especially regarding part d: are we counting the number of times that the loop runs, or the number of times that the statement is printed? Therefore, change the problem to read "Indicate whether the number of times that output is printed is O(n) or O(n2)."

Question 2: The textbook is a little inconsistent throughout section 2.8 as to whether it uses "strictly greater than" or "greater than or equal to" when showing if T(n) is O(f(n)). (In the middle of page 113, you see the expression cf(n) >= T(n); but later on the same page, in example 2.19, you see cn2 > n2 + 5n + 25.) It actually doesn't matter which kind of inequality you use, since either way leads to precisely the same big-O conclusions. However, just to keep this particular problem consistent and clear for everyone (and to make the grader's life more straightforward), you should consider it to read as follows: "For the following T(n) find values of n0 and c such that cn3 is larger than or equal to all n larger than n0."