Time complexity of finding max value in list using recursive bsearch

user_8572173 0
Viewed 760

Sorry if this seems like a dumb question (I am new to Big O) but what is the difference between a) the time complexity of this function based on its no. of comparisons vs. b) the time complexity of the function overall?

def bmax(list):
   if len(list) == 1:
       return list[0]
   else:
       middle = len(list)//2
       max1 = bmax(list[0:middle])
       max2 = bmax(list[middle:len(list)])
       if max1 > max2:
          return max1
       else:
          return max2

I derived it to be a) O(n) and b) O(logN) respectively but the second answer seems off because based on my understanding, although the list is always divided into 2 sub arrays at each recursive call, the number of comparisons is still n-1?

binary-search max recursion algorithm python
2 Answers
  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))
user_52961060

As you correctly pointed out, the complexity is still O(n) here, because you still have to do all the comparisons.

However, if I'm not mistaken if the recursive calls to bmax is done in another thread for parallel execution, and you have infinitely many threads, the function will finish in O(log(n)) time.

user_35463330
Related