Time complexity

Question

Given a 2D array X[m][n] which has m rows and n columns. The array X is row wise and column wise sorted (i.e) each individula row and column is sorted. What is the complexity to search an element in this array

a)O(m*n)

b)O(m2) or O(n2)

c)O(log2(m*n))

d)O(m+n)

Answer 1

option D

Comments

how???

My logic

the individual rows and columns are sorted

lets consider elements 1 , 2 , 3, 4,5,6,7,8,9

row sort it - 4 5 6

                   1 2 3

                  7 8 9 

columns sort it-   1 2 3

                              4 5 6

                              7 8 9

now store it in row major order - 1 2 3 4 5 6 7 8 9 will be the sequence

on this apply binary search

therefore O( log2(m*n))

correct me

Answer 2

You can binary search on each column.This might seem O(logm*logn) but it actually is min O(m*logn,n*logm).The answer can be both A and B.