Recurrence Relations

Worst Case Analysis

Average Case Analysis

Binary Search

Analysis of BinS: Basis

Analysis of BinS: Recurrsion I

Analysis of BinS: Recurrsion II

Analysis of BinS: Recurrence

Solving the Recurrence

Continuing the Exercise ...

Ah Ha! A General Formula!

Ah Ha! A General Formula!

Ah Ha! A General Formula!

Ah Ha! A General Formula!

Ah Ha! A General Formula!

Ah Ha! A General Formula!

When Will W disappear?

When Will W Disappear?

When Will W Disappear?

Finally ...

Some Other Recurrences

Recurrences with T(1)=1

The Challenger

The Master Theorem I

The Master Theorem II

The Master Theorem III

Homework