Give an $O(n+m)$-time algorithm to determine whether a given number is stored in a given $m\times n$ Young tableau. An $m\times n$ Young tableau is an $m\times n$ matrix such that the entries of each row are in sorted order from left to right and the entries of each column are in sorted order from top to bottom. Task has got simple solution (I saw answers after my algorithm), but I made my own. I am not sure about its time complexify.
Algorithm: Let $x$ – required number. Assume we have matrix $A$ $n\times n$ (if not we can split matrix). If $x > A[n][n]$ or $x < A[1][1]$ return false. If not, we can find with binary search $k: A[k][k]=x$ (return true) or $i,j: A[i][i]< x < A[j][j]$. Since tableau is Young, $A[j\dots n,j\dots n]>x $ and $A[1\dots i,1\dots i] < x$ so $x \notin A[j\dots n,j\dots n]$ and x $\notin A[1\dots i,1\dots i]$. Then we have two another matrixes with smaller size where $x$ may be: $A[1\dots i ,j\dots n]$, $A[j\dots n,1\dots j]$. $i^2+j^2$ (elements of throw matrixes) > $i*j + j*i$ (elements of new matrixes), so $T(n)<= 2T(n/2) + \theta(\lg n)$
I tried: At each recurrence step in the worst case (number not exist in matrix and two split points in the middle at each iteration) we have two matrixes to solve with size ~$n/2$. We also made binary search with diagonal elements so $T(n)=2T(n/2) + \theta(\lg n)$. By master theorem $T(n)= \theta(n)$.
If split points not central then
So $T(n) = O(n)$ in base case.
Question:Is my analysis wrong?
Best Answer
No, your recursion may end up finding one extreme corner of the matrix as the "split" point and then your algorithm will be $\Theta((m+n) \log(m+n))$. The traditional approach to this problem to get your desired complexity is to test, say, an upper-left corner where everything to the right of the corner in the row is greater than, and everything below the corner in the column is less than. Then you either find your desired number at the corner, or you eliminate either one row or one column from the search. By continuing this way always testing corners, at most you have to test $m + n$ corners before all rows and columns are eliminated (in which case, your number is not in the table). So complexity is $O(m + n)$.