The Gateway to Computer Science Excellence
+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.$
in Algorithms by Boss (16.8k points)
edited by | 20 views

1 Answer

0 votes
(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)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,492 answers
195,439 comments
100,694 users