3. Suppose We have a 2-dimensional structure with n rows. The rows are indexed 1,2,..., n...

 

Transcribed Image Text:

3. Suppose We have a 2-dimensional structure with n rows. The rows are indexed 1,2,..., n and row k is a list of length k. Each row in the array is sorted. To perform a binary search on the structure, we iterate through the rows and binary search each. Assume in the worst case that it takes Clg k + D to perform a binary search on a sorted list of length k, where C, D > 0 are fixed constants. (a) What is (b) What is of the best case? Justify. of the worst case? Justify. 3. Suppose We have a 2-dimensional structure with n rows. The rows are indexed 1,2,..., n and row k is a list of length k. Each row in the array is sorted. To perform a binary search on the structure, we iterate through the rows and binary search each. Assume in the worst case that it takes Clg k + D to perform a binary search on a sorted list of length k, where C, D > 0 are fixed constants. (a) What is (b) What is of the best case? Justify. of the worst case? Justify.

Answer rating: 100% (QA)

SOLUTION a Best case In the best case all the elements in each row are sorted in increasing order an... View the full answer