Suppose that I had 1000 records stored in alphabetical order and I wanted to use

Question

Suppose that I had 1000 records stored in alphabetical order and I wanted to use binary search to find one of them. What is an upper bound on the number of different records I could have to look at? 1 9 10 1000 Suppose that I searched for a number x in a sorted list of n items by comparing against the 5th item, then the 10th, then the 15th, etc. until I found an item bigger than x, and then I searched backwards from that point. Which expression best describes the approximate running time of this algorithm: n log n n^2 Suppose that I ran merge sort, but I could magically merge two sorted lists of any length in 1 unit of time. Which expression best describes the approximate running time of this algorithm: 1 n n log n

Explanation / Answer

1 Answer) 10

Explantion: The worst case running time of binary search is log(n) . So log(1000) = 10 is the correct answer

2 Answer) n

3 Answer) n

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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