Lecture 23: 03/21/2012

We’re done with Treaps today.

At first we covered some of the intuition as to why the expected time to find an element m in a random treap is O(log n).

The analogy used is that of a dart game. You throw darts at the board numbered 1 to n and the first dart is the root of the treap. Then you ignore everything to the left or everything to the right, depending on whether m is to the right or left of the first dart, respectively, and repeat the process until you hit m.

In expectation, you’re throwing out roughly half of the elements with each dart, so the expected time to find m is O(log n).

Formally, we proved the bound by solving a recurrence relation for the expected cost to search for a particular element in the random treap.

On Friday we’re covering Planar graphs, which will motivate the Planar separator theorem. Make sure to skim through the chapter to get the basic definitions and come up with some really good questions.

Enjoy the beautiful weather!