Following algorithm finds max QAZ. QAZ of an element is number of elements with higher value after that element's index. The popular answer is to use divide and solve using O(nLog(n))..
The array is not sorted. In worst case 'Divide&Conquer' will touch all n elements. Also 'for loop' will touch n/2 elements at worse.. How is it n*log(n).. Shouldn't it be O(n^2).. thanks
class QAZ:
def __init__(self, min, qaz):
self.min = min
self.qaz = qaz
def max_qaz(arr):
n = len(arr)
def max_qaz_util(start, end):
if end <= start:
return QAZ(arr[end], 0)
elif start == (end + 1):
return QAZ(arr[start], 1) if arr[start] < arr[end] else QAZ(arr[end], 0)
mid = int((start + end) / 2)
left = max_qaz_util(start, mid)
right = max_qaz_util(mid + 1, end)
if left.min < right.min:
left.qaz += end - mid
return left
else:
for i in range(mid + 1, end + 1):
if arr[i] > left.min:
left.qaz += 1
return left if left.qaz > right.qaz else right
result = max_qaz_util(0, n - 1)
print("minval", result.min)
print("qaz", result.qaz)
max_qaz([33, 25, 26, 58, 41, 59])
Yes, the for loop touches n/2 elements in the worst case. The important fact here is that the division of the input is as even as possible. The amount of work done by the algorithm on n elements is O(T(n)), where the recurrence T is defined by
T(1) = O(1)
T(n) = 2 T(n/2) + O(n).
Case 2 of the Master Theorem applies, so T(n) = O(n log n). This is very similar to merge sort.