Consider the problem of searching in a sorted matrix. That is, you are given an

Question

Consider the problem of searching in a sorted matrix. That is, you are given an n × n matrix A, where each entry is an integer. Each row of the matrix is sorted in ascending order, and each column is also sorted in ascending order. Given a value x, the problem is to decide whether x is stored somewhere in the array (i.e., whether there is some i and j such that A[i][j] = x).

A) One way to solve this problem is to do binary search in each row. What is the worst-case running time of this algorithm (in terms of n)?

B) Give a divide-and-conquer algorithm for this problem. (Hint: Your algorithm needs to call itself recursively, so think carefully about the parameters required. First compare x with the element in the “middle” of your array (i.e., middle row, middle column). Then ...?).

C) Write down a recurrence equation describing the running time of your algorithm from (b).

D) Solve your equation from (c), using the formula for solving divide-and-conquer recurrences discussed in class.

E) Based on your answers to the above questions, which algorithm for solving the problem is faster: binary search in each row or the divide-and-conquer algorithm from part (b)?

Explanation / Answer

Solution:

a)

If we are solving row by row and each row has n elements, so the recurrence relation will be T(n) = nT(n/2) + c

we know that binary search takes O(log n) (in the worst case) time to search from an array of n elements which is already sorted and here we have n such rows so the worst case time complexity

T(n)= O(n log n)

b)

Algorithm:

Begin
Find the middle element
If key is same as the middle element return the middle element
If the key is smaller than the mid element
search vertical submatrix on the left side of the middle element
search submatrix on the right-hand side.
If the key is greater than the middle element then
3a) search submatrix on the lower side of the middle element
Search submatrix on the right-hand side.of the middle element
c)

The recurrence relation is T(n) = 3T(n/2) + c

d)

According to Master's theorem,

here a= 3, b= 2, and f(n)= c

So,

n^(logb a)= n^1.585

comparing f(n) and n^(logb a) this is case 1 of Mster's theorem

so the time complexity T(n)= Theta(n^1.585)

e)

comparing the two algorithms binary search is still faster of these two.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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