suppose that even unrealistically, we are to search a list of 700 milloin items

Question

suppose that even unrealistically, we are to search a list of 700 milloin items using Binary search, recursive. What is the maximum number of comparisons that this algorithm must perform before finding a given item or concluding that it is not in the list

1. Use Binary Search, Recursive (Algorithm 2.1) to search for the integer 120 in the following list (array of integers. Show the actions step by step. 12 34 37 45 57 82 99 120 134 2. Suppose that, even unrealistically, we are to search a list of 700 million items using Binary Search, Recursive (Algorithm 2.1). What is the maximum number of comparisons that this algorithm must perform before finding a given itemor concluding that it is not in the list?

Explanation / Answer

Since we are talking about binary search, let's assume that the items are sorted according to some criteria.

Time complexity of binary search is O(logN) in worst case, best case and average case as well. That means it can search for an item in Log N time where N is size of the input. Here problem talks about the item not getting found. So, this is a worst case scenario. Even in this case, binary search runs in O(logN) time.

N = 700000000.

So, number of comparisions can be log(N) = 29.3 = 29.

So, in the worst case it does comparisions 29 times

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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