There are many ways to support a dictionary (set, on which the operations of insert, delete, and lookup can be performed). Among these are various types of hash tables, binary search trees, and various kinds of balanced-search-tree schemes. These schemes offer different per-operation running times, both in the worst-case and expected-case senses. Analyze each of the following schemes, both for the worst and expected cases. A tight big-oh approximation is sufficient, assuming n is the number of elements currently in the set.

1. A chained hash table with n/(log n) buckets.
2. A binary search tree.
3. A hash table using open addressing and quadratic probing, with 2n buckets.
4. A balanced binary tree such as a 2-3 tree.

Referring to these as "schemes 1, 2, 3, and 4," find the true statement below. Note that a statement like "scheme x is O(y)" should be interpreted as meaning "is O(y) but not of any significantly lower running time." Formally, we mean that the running time is also big-omega of y.

a) Scheme 3: Expected O(n)
b) Scheme 1: Worst-Case O(1)
c) Scheme 4: Expected O(1)
d) Scheme 4: Worst-Case O(log n)