Homework 2 - B Term 2005

See course policy regarding late homework submissions

- Read Chapter 2 of the textbook in detail.
**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 n ^{2}n ^{3}100 n ^{2}n log n 2 ^{n}2 ^{2n}**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:
- Is 2
^{n+1}= O(2^{n}) ? - Is 2
^{2n}= O(2^{n}) ?

- Is 2