### CS2223 Algorithms Homework 2 - B Term 2005

#### PROF. CAROLINA RUIZ

Due Date: November 8th, 2005 at 2:00 PM
See course policy regarding late homework submissions

1. Read Chapter 2 of the textbook in detail.

2. Problems: You need to turn in a hard copy of your written solutions to the following exercises at the beginning of class on the day the homework is due. Remember to show your work and explain your answers. Correct answers without complete explanations won't receive full credit. Incorrect answers with explanations may receive partial credit.

• Chapter 2: exercise 1.

• Chapter 2: exercise 2.
Solve execise 2 and add to it the following parts: within 1 second? within 1 minute? within 1 day? within 1 month? within 1 year? within 1 century? That is, your solutions to this exercise should contain a table like the one below together with explanations for each of the values you provide in your table.
 1 second 1 minute 1 hour 1 day 1 month 1 year 1 century n2 n3 100 n2 n log n 2n 22n

• Chapter 2: exercise 3.

• Chapter 2: exercise 5.

• Chapter 2: exercise 6.

• Let f(n) and g(n) be two non-negative functions, and let max(x,y) be the function that returns the maximum between its given arguments. Using the basic definition of Θ-notation, prove that max(f(n),g(n)) = Θ(f(n) + g(n)).

• For each of the following statements, determine if the statement is true or false, and in each case provide a detail explanation/proof of your answer:

1. Is 2n+1 = O(2n) ?

2. Is 22n = O(2n) ?