Speaker: Jonathan Derryberry

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Lower Bounds for the Binary Search Tree Model

Abstract:

This talk considers the problem of bounding below the cost of
accessing a sequence of keys in a binary search tree. We develop a
simple lower bound framework for this problem that applies to any
binary search tree algorithm, including self-adjusting and offline
ones. This new framework can be used to derive two previously known
lower bounds.