+1 vote
20 views

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.$

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

edited | 20 views

(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.
by Boss (13.2k points)

+1 vote