Python3 O(n + m) with explanation/proof
Consider the submatrix whose upper right corner is index i, j (row, column) and whose bottom left corner is the bottom left of the original matrix.  Suppose we 
Consider the submatrix whose upper right corner is index i, j (row, column) and whose bottom left corner is the bottom left of the original matrix.  Suppose we know that the element we are searching for is either in this submatrix, or it is not in the matrix at all.  If the target is greater than matrix[i][j] then we know the target is not in row i and we can now consider the submatrix whose upper right corner is i - 1, j .  If the target is less than matrix[i][j] then we know that the target is not in column j and we can now consider the submatrix whose upper right corner is i, j-1.  Initially we know that the element we are searching for is either in the matrix or it is not.  In other words, we initially know that the element we are searching for is either in the submatrix whose upper right corner is at 0, m - 1 (where m is the number of columns) or it is not in the matrix at all.  The idea of the algorithm is to maintain with each iteration the condition that the target is in the submatrix whose upper right corner is index i, j.\n\n```\nclass Solution:\n    def searchMatrix(self, matrix, target):\n        if matrix == None or len(matrix) == 0 or len(matrix[0]) == 0: \n            return False\n        n, m = len(matrix), len(matrix[0])\n        i, j = 0, m - 1\n        while i < n and j >= 0:\n            if matrix[i][j] == target:\n                return True\n            elif matrix[i][j] < target:\n                i += 1\n            else:\n                j -= 1\n        return False\n\t\t```
['Python', 'Python3']