Python, O(log(4/3, M) + log(4/3, N)) recursive, but slower than O(m+n) loop algorithm


  • 0
    C

    The O(m+n) loop code is everywhere in the discussion, here I post my O(log(4/3, M) + log(4/3, N)) code, but it is much slower in time. I guess it is because of the recursion. Any idea?

    class Solution(object):

    def searchMatrix(self, matrix, target):
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        rowL = 0
        rowH = len(matrix) - 1
        colL = 0
        colH = len(matrix[0]) - 1 
        return self.binarySearch(matrix, rowL, rowH, colL, colH, target)
    
    def binarySearch(self, matrix, rowStart, rowEnd, colStart, colEnd, target):
        if rowStart > rowEnd or colStart > colEnd:
            return False
        if rowStart == rowEnd and colStart == colEnd:
            if matrix[rowStart][colStart] == target:
                return True
            else:
                return False
        rowM = (rowStart + rowEnd) / 2
        colM = (colStart + colEnd) / 2
        if matrix[rowM][colM] < target:
            #search all blocks except upper left block
            return self.binarySearch(matrix, rowM+1, rowEnd, colStart, colEnd, target) \
                or self.binarySearch(matrix, rowStart, rowM, colM+1, colEnd, target)
        elif matrix[rowM][colM] > target:
            #search all blocks except right bottom block: upper right, upper left
            return self.binarySearch(matrix, rowStart, rowM-1, colM+1, colEnd, target) \
                or self.binarySearch(matrix, rowStart, rowM, colStart, colM, target) \
                or self.binarySearch(matrix, rowM+1, rowEnd, colStart, colM-1, target)
        else:
            return True

  • 0
    C

    Maybe the test data is not big enough.


  • 0
    Z

    It is not log-complexity as you claimed. Based on the Master's Theorem, the complexity should be
    (m*n)^(log_{4} 3), which is lower than linear, but much higher than log.
    However, this is only some kind of "order" (we do not exactly know the factor before it), that's why the exact linear algorithm may perform better than this (also considering the computational cost introduced by recursion)


  • 0
    C

    Sorry I am wrong. I think it should be log(4/3, m*n), right?


  • 0

    @cfdream log(mn) and log(m)+log(n) are the same, so they're equally wrong.


  • 0

    Linear algorithm performs better because (mn)^(lg4(3)) is not exactly lower than linear. It is lower than linear in terms of mn, but the linear algorithm is linear in terms of m+n. For example, if we consider nxn case, then the linear algorithm will be 2n and this one will be n^(2lg4(3)) = n^(lg2(3)) ~ n^1.58, which is certainly worse than 2n.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.