25
Apr
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.
