CODEWITHSUNDEEP
algorithmtime-complexitybig-ocomplexity-theory
qwerty12456
qwerty12456

Reputation: 33

Time complexity of O(log n) in double nested loop function

I don't know how to calculate time complexity of this algorithm, I know nested loops is O(n^2) but i don't know what to do with .insert(), I came to wrong conclusion about it being O(n^2 + n log n) but I know I can't sum in big O, any help would be appreciated.

for i in range(arr_len):
     for j in range(arr_len):
         if (i == arr[j]):
             max_bin_heap.insert(//whatever) //O(log n)

Upvotes: 3

Views: 2106

Answers (1)

Miljen Mikic
Miljen Mikic

Reputation: 15251

At first glance, most people would say that this is O(n*n*logn) because of two nested loops and O(logn) operation max_bin_heap.insert call within the inner for loop. However, it is not! Pay attention to if (i == arr[j]) condition. For each j from the inner for loop, at most one value of i will be equal to arr[j], so two for loops will not induce n^2 invocations of max_bin_heap.insert call, but only n of them. Since there are n^2 comparisons and at most n*logn heap operations, the total complexity is O(n*logn + n*n) = O(n^2).

Upvotes: 5

Related Questions