Now consider the problem of finding the rank of a key. How many array accesses does this take for an ordered array based symbol table?

constant

logarithmic

linear

linearithmic

Suppose we instead implement our symbol table with a binary search tree. What is the maximum number of compares needed to search for a key in such a symbol table?

constant

logarithmic

linear

linearithmic

Suppose we build a binary search tree by inserting the keys in a random order. What is the expected number of compares needed to find the rank of a key?

constant

logarithmic

linear

linearithmic