Time complexity of finding max value in list using recursive bsearch

  1. The time complexity of this function based on its number of comparisons can be derived by “counting” how many comparisons are performed when calling the function on a list with N elements. There are two statements where you directly use comparisons here: len(list) == 1 and max1 > max2. There are clearly O(N) comparisons.
  2. The time complexity of the function overall must take into account all the statements. So it will be at least equal to the previous complexity (therefore it can’t be O(logN)). In this specific case, slicing operations do cost a lot. In general, the operation l[i1:i2] costs O(i2-i1). For more details, check out this question. So I would say that the total time complexity is O(N^2) in this case. If you want to improve the performance, you could pass the indexes instead of using slicing.
def bmax(lst):
    def _bmax(start, end):
        if end - start <= 1:
            return lst[start]
        else:
            middle = start + (end - start) // 2
            max1 = _bmax(start, middle)
            max2 = _bmax(middle, end)
            if max1 > max2:
                return max1
            else:
                return max2
    return _bmax(0, len(lst))

If you want to simplify a bit your code:

def bmax(lst):
    def _bmax(start, end):
        if end - start <= 1:
            return lst[start]
        middle = start + (end - start) // 2
        return max(_bmax(start, middle), _bmax(middle, end))
    return _bmax(0, len(lst))

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top