The analysis of binary search in this chapter assumed that the size was always 2k 1 for some value of k. For this question, we will explore other possibilities for the size:

a. What is the worst case when N 2k 1?

b. What is the average case when N 2k 1, assuming that the key is in the list? Hint: Think about what this change in size means for the bottom of the search tree.

c. What is the average case when N 2k 1, if the key might not be in the list? Hint: Think about what this change in size means for the bottom of the search tree.