Work individually on this assignment.

Problem 1. (3 pts. per part) Determine if the following statements are true or false and prove your answers. To prove a statement is true, specify the needed constants and show the definition holds for them.

1. 2 lg n = O(sqrt(n))
   
   
2. 4 n lg n = O(n²)
   
   
3. n² = O(n)
   
   
4. 2 + 3 n + 2 n²/2 = Θ(n²).
   
   
5. lg 2ⁿ is Θ(n²).
   
   

Problem 2. (4 pts.) Assume that f(n) = O(g(n)). Can g(n) = O(f(n))? Are there cases where g(n) is not O(f(n))? Prove your answers (give examples for the possible cases as part of your proofs, and argue the result is true for your example).

Problem 3. (5 pts. for each part) Solve the following recurrences using the recursion tree method. For full credit, show your work. I realize that some of you will be able to write the answer by inspection after the next lecture and recitation, but I want to see that you understand where the answers come from.

Hint: See p.~1147 of the text on summing geometric series and recall some logarithm properties in order to get a closed-form solution in terms of a polynomial in n for part (a).

(a) T(n) = 5 T(n/3) + 1, where T(1) = 1

(b) T(n) = 4 T(n/4) + n, where T(1) = 0

// Program to compute the squares from 1 to m

PrintSquares(m)
  for j = 1 to m
      result = Square(j)
      print result

// Function to compute kth square

Square(k)
  total = 0
  for i = 0 to k-1
      total = total + 2*i + 1
  return total