The analysis of binary search in this chapter assumed that the size was always 2

Question

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.

Explanation / Answer

a) When N 2k - 1

The worst case is when the key is not in the list.

Now, either N > 2k - 1 or N < 2k - 1.

In both cases, N < 2k+1 - 1

Hence the binary tree will have a height of k when few nodes of the bottom of the tree being empty.

Hence, the complexity will be O(k+1) = O(logN) (Here, k+1 = log2N).

b) Again by the same assumption, N < 2k+1 - 1, which results in a binary tree of height k.

In average case, we need to check (k+1)/2 nodes which gives a complexity of O(logN/2) = O(logN).

c) As with a) if the key is not in the list we get O(log N).

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.