CMI2019-B-6

Question

Let $A$ be an $n\times n $ matrix of integers such that each row and each column is arranged in ascending order. We want to check whether a number $k$ appears in $A.$ If $k$ is present, we should report its position - that is, the row $i$ and column $j$ such that $A(i,j)=k.$ Otherwise, we  should declare that $k$ is not present in $A.$

• A. Describe an algorithm that solves this problem in time $O(n\log n).$ Justify the complexity of your algorithm.
• B. Describe an algorithm that solves this problem by examining at most $2n$ values in $A.$ Justify the complexity of your algorithm.
• C. For both algorithms, describe a worst-case input where $k$ is present in $A.$

Comments

This exact question was asked in JEST 2022 in TCS exam

Answer 1

(a) Since, each row is sorted in the ascending order therefore we can use Binary search on each row, which works in $O(logn)$ time.

For $n$ rows, time complexity $=$ $O(nlogn)$

 

PS will write b and c by evening.

Comments

(1) is kind of Peak finding question just with a little variation , we can do it in O(logN * logM) time

where N,M are rows and column of matrix.

Answer 2