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!

  • 1
    $\begingroup$ Size $n$ meaning that it is $n \times n$? $\endgroup$ – dalastboss Mar 15 '15 at 21:06
  • $\begingroup$ Yes, I think, I'll change it to $n\ \times\ n$ $\endgroup$ – 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)<X$.

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.

See also here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.