- 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) == 1and
max1 > max2. There are clearly O(N) comparisons.
- 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.