University of California, Santa Cruz

Prof. Paulo Franca - Spring 2000

Introduction

Syllabus

Guidelines for labs

Lab sections

Take quiz & check grades

Recurrences

Purpose of this chapter:

to let you compute the bounds on the running time of a given algorithm when the expression for T(n) is not readily available as a function of n. T(n) is available as a recurrence.

3 methods:  (pages 53 to 64)

bullet
substitution method
bulletguess a bound and use mathematical induction to prove the guess correct
bullet
iteration method
bulletconverts the recurrence into a summation and try to find the solution
bullet
master method
bulletcan only be used for recurrences of the form T(n)=aT(n/b) + f(n). It does not cover all the cases.

Recurrences:

The running time is expresssed by a recurrence relation:

Example:

T(n) is:

bulletTeta(1) if n=1
bullet2* T(n/2)+Teta(n) if n>1