2

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?

Emma
  • 27,428
  • 11
  • 44
  • 69
Jane Doe
  • 79
  • 8
  • While is fine to study that algorithm in order to learn, in reality it is worse than just going through the array element by element to find the max, so you should probably be aware of that – pygri Oct 30 '20 at 15:50

2 Answers2

1
  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))
Riccardo Bucco
  • 13,980
  • 4
  • 22
  • 50
  • Thank you for simplifying the code for me. Just want to ask what are your views on Anthony's response, whether the recursions are done in parallel? – Jane Doe Oct 30 '20 at 16:20
  • @JaneDoe First of all DON'T use slicing. It is a nice operation, but it hides a "high" time complexity. Simply use indexes to access your data. If you had infinite many threads, the complexity would be log(N) as long as you don't use slicing :) Realistically, this cannot be done. Also, creating a thread is itself an operation that has some complexity. So I would not rely on parallel computation for such a problem. Also, doing parallel computations would require a much more difficult code. – Riccardo Bucco Oct 30 '20 at 16:23
0

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.

anthony-khong
  • 141
  • 2
  • 4
  • Thanks Anthony, for me it didn't seem like it is done in parallel since the recursion of max1 is executed and completed first before moving on to the recursion of max2? Correct me if I'm wrong – Jane Doe Oct 30 '20 at 16:22
  • @JaneDoe you're right. Anthony is talking about an ideal situation, not this specific one – Riccardo Bucco Oct 30 '20 at 16:26