Time Complexity

Question

Comments

It is D)., but we can reduce it to A).

A). should be right .

---

A is answer in worst case we have to traverse one full row then full column only.

It is like robot problem.

Answer 1

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.