SUNY Geneseo Department of Computer Science

Problem Set 8 -- The Master Theorem

CSci 240, Spring 2007

Prof. Doug Baldwin

Due Tuesday, February 27

Purpose

The goal of this exercise is to develop your ability to apply the Master Theorem to finding asymptotic closed forms for recurrence relations.

Background

This exercise deals with the Master Theorem, which we discussed in lecture on February 19 and February 21.

Exercise

Find asymptotic closed forms for each of the following recurrence relations.

Recurrence 1

T(n) = 1 if n = 0
T(n) = 8 T(n/2) + n if n > 0

Recurrence 2

T(n) = 1 if n = 0
T(n) = 9 T(n/3) + n² if n > 0

Recurrence 3

T(n) = 17 if n = 1
T(n) = 3 T(n/2) + n² if n > 1

Recurrence 4

T(n) = 1 if n = 0
T(n) = 2 T(n/4) + 2 if n > 0

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Make an appointment to meet with me at some time convenient for you, as long as that time is before the end of the due date above. Meetings only need to be 15 minutes long. You can make an appointment by signing up on the copy of my schedule on the bulletin board outside my office. Please bring written solutions to each of the problems to the meeting.