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!