364 views
1 votes
1 votes

1 Answer

0 votes
0 votes

O(m+n)

We can use a variation of linear search begining from top right or bottom left corner and we can move left or bottom( if we start from top right corner) after making comparisons.

Ex. searching for a number say 4 occurs in this way starting from top right corner. blue cells is the path to reach 4.

1 3 5 8
4 9 10 12
6 13 14 15

worst case occurs when number to be searched is at  opposite end of matrix , in that case m+n steps have to be taken to reach the opposite side.

Related questions

2 votes
2 votes
1 answer
2
1 votes
1 votes
2 answers
3
Ashwani Kumar 2 asked Sep 8, 2016
373 views
What is the running time of following recurrence relation?T(n) = T(n/2) + T(n/4) + T(n/8) + n