CS200 Spring 2016 HW2

Procedure

Create a plain text file called hw2.txt, which looks like this: 
    Q1a:
    answer for question #1a

    Q1b:
    answer for question #1b
    …
Turn it in via web checkin, or like this: 
    ~cs200/bin/checkin HW2 hw2.txt
Do not turn in a paper copy.

Notation

For this assignment, use a^b to represent ab. Use parentheses for non-trivial exponents: Does 2^n+1 mean 2^(n+1) or does it mean (2^n)+1 ?

Simplifying

Simplify your answers. I do not want to see: O(17⋅2n⋅log3n+42)
I want this, instead: O(2n⋅log n)

The Master Theorem

For reference, here is the Master Theorem:

Let f be an increasing function that satisfies f(n) = a⋅f(n/b) + c⋅nd whenever n = bk, where k is a positive integer, a≥1, b is an integer > 1, and c and d are real numbers with c positive and d nonnegative. Then

  O(nd) if a < bd
f(n) =   O(nd log n)   if a = bd
  O(nlogba) if a > bd

Questions

  1. What are the big-O bounds of these recurrence relations?
    1. f(n) = 2⋅f(n/2) + 1
    2. f(n) = 2⋅f(n/2) + n
    3. f(n) = 2⋅f(n/4) + n
    4. f(n) = 4⋅f(n/2) + n
    5. f(n) = 4⋅f(n/4) + n
    6. f(n) = f(n/2) + 1
  2. Which of the above describes the complexity of
    1. Binary Search
    2. Merge Sort
  3. Given the following methods: 
        public int recMax (int[] A) {
	return recMax(A, 0, A.length-1);
    }
    private int recMax(int[] A, int lo, int hi) {
	if (lo==hi)
	    return A[lo];
	else {
	    int mid = (lo+hi)/2;
	    int m1 = recMax(A, lo, mid);
	    int m2 = recMax(A, mid+1, hi);
	    return Math.max(m1, m2);
	}
    }
    1. Derive a recurrence rM(n) relation for recMax(A, lo, hi), where n = hi-lo+1.

           rM(n) = 1    for n = 1
           rM(n) = ?    for n > 1

    2. Use the Master Theorem to solve the recurrence and obtain the big O complexity of recMax.

      rM(n) = O( ? )

  4. Find a closed-form solution to the following recurrence relation, using repeated substitution: