CS 70

Before You Start

Let's consider the operation getMin(), which returns the smallest key in a set.

What would be the complexity of getMin() for a balanced BST?

To find the minimum key, we need to start at the root and then keep going left until we can't go any further.

This process will follow a single path from the root down to a leaf which, in a balanced tree, we know has length \( \Theta(\log n) \).

What would be the complexity of getMin() in an open-addressing hash table? (Assume that \( \lambda \) is a constant).

We have no idea where the minimum key is stored in a hash table, so we have no choice but to look at all the keys!

Worse than that, we also have to look at the empty buckets just to see that they are empty.

So, for an open-addressing hash table with \( M \) buckets, this search takes \( \Theta(M) = \Theta( n\, / \lambda ) = \Theta(n) \) time.

  • Rabbit speaking

    Probably there is a clever way to avoid looking at the empty buckets, but doing so would make the code more complicated.

  • LHS Cow speaking

    And more to the point, it would still be \( \Theta(n) \) time, just with a smaller constant factor.

(When logged in, completion status appears here.)