# Find minimum algorithm complexity

So, I have this task: Let us have square matrix $A \ size\ n\ \times\ n$ for which is true: $$A(k,l)<=A(m,p)\ if \ k <=m, l<=p$$ I need to find algorithm, which finds value X in such matrix, which is not very hard, it combination of binary search, first to find row(or column), and then binary search in row(or column) which will be $~nlog(n)$. But second task is: prove that there is no algorithm which will do it for $O(n)$ time complexity that is the point where I'm stuck. I know how to calculate complexity of some algorithm, but I don't know how to prove that my algorithm is fastest.

Thank you!

• Size $n$ meaning that it is $n \times n$? – dalastboss Mar 15 '15 at 21:06
• Yes, I think, I'll change it to $n\ \times\ n$ – DoctorMoisha Mar 16 '15 at 19:02

I think this is not correct. The problem can actually be solved in $$O(n)$$.

Consider the following algorithm: Find the matrix element by starting in the top right corner at element $$A(1, n)$$ and moving towards the lower left corner $$A(n, 1)$$. In each step return $$A(k,l)$$ if $$X=A(k,l)$$, move left (i.e. decrease $$l$$) if $$X>A(k,l)$$ and move down (i.e. increase $$k$$) if $$A(k,l).

Too see that this works, consider the upper right submatrix with elements $$A(i,j)$$ for $$i=1,\ldots,k$$ and $$j=l,\ldots,n$$ for $$A(k,l)=X$$. When walking from $$A(1,n)$$ towards $$A(n,1)$$, we are leaving the upper right submatrix along the row or column where $$X$$ lies. We must pass $$X$$, because on the row where $$X$$ lies all elements on the right side of $$X$$ are large then $$X$$, so each step is a left move. In the same way if we are on one of the elements in the column where $$X$$ lies, each following step will be a down move.