Problem Set 6—The Master Method

Purpose

Background

Exercise

Solve each of the following problems.

Problem 1

For which of the following recurrences does the Master Method allow you to find an asymptotic closed form? For each that it does, say which case applies; for each that it does not, say why not. In all cases, assume that T(0) = 1.

1. T(n) = 2 T(n-1)
2. T(n) = 2T(n/2) + n - 1
3. T(n) = n T(n/3) + log n

Problem 2

Find asymptotic closed forms for the following recurrence relations. In all cases, assume that T(0) = 1:

1. T(n) = 9 T(n/3) + n³
2. T(n) = T(n/2) + n²
3. T(n) = 4 T(n/2) + n²
4. T(n) = 2 T(n/4) + 1

Problem 3

I once asked a class to experimentally verify the Θ(log n) execution time of binary search using a recursive implementation of the algorithm such as this:

    search( A, k, low, high )      // Return the position at which k is found in A, or -1 if not found
        if high < low
            return -1
        else
            mid = ( low + high ) / 2
            if k < A[mid]
                return search( A, k, low, mid-1 )
            else if k > A[mid]
                return search( A, k, mid+1, high )
            else
                return mid

Unbeknownst to me, the language in which I had coded this algorithm passed arrays to function calls by copying them, thus taking Θ(n) time just to set up, let alone actually execute, the recursive calls in the algorithm. What was the actual asymptotic execution time of the program I gave these students?

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Please bring a written solution to your meeting. During the meeting, I will look over your solution, give you my reactions to it, answer any questions you have about it, etc.

Meetings should take about 15 minutes, although you are welcome to reserve a longer time if you have a lot of questions. Please sign up for your meeting on the schedule outside my office. If you work in a group, the entire group can schedule a single meeting with me. You should be ready to grade this exercise shortly after class on the “Complete By” date above; however, you have until the end of the “Grade By” date to actually meet with me.