You are given a two-dimensional n times n square matrix A. Each row of A is sort

Question

You are given a two-dimensional n times n square matrix A. Each row of A is sorted left to right; each column of A is sorted from top to bottom. Consider the following algorithm for finding the row and column of a given target element. Algorithm: examine the element in the middle of the matrix. Make recursive calls after comparing this element with the target. Consider the picture above. Suppose the element we examine (highlighted) is smaller than the target. Which sections of the matrix still need to be searched? What is the running time of the previous algorithm?

Explanation / Answer

We wil be searching in B, C, D

All element in A will be smaller than highlighted and hence our item will not be there

Previous algorithm is not provided.

This algorithm will prune 1/4th of the matrix in each call so for n*n matrix

T(n) = 3*T(n/2) + O(1)

Solving using masters method will give O(n^1.58)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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