CODEWITHSUNDEEP
time-complexitybig-ocomplexity-theory
Raxhacks
Raxhacks

Reputation: 39

Time complexity of this function O(n^2logn)?

I'm trying to figure the time complexity of this function out: Pseudo-code

def inc(m):
  if m>12:
     return;
  for i in range(1,m):
     //some code
  mergeSort(array,0,n-1)
  for j in range(1,m):
     //some code
  inc(m+=1);

Is the time complexity O(n^2logN)? as you can see, this example is of a recursive function calling a differente recursive function for sorting and at the end itself. I don't know if the for loops affect and also the calling of another recursive function as merge sort.

Upvotes: 0

Views: 92

Answers (1)

Abdulhakeem
Abdulhakeem

Reputation: 153

The time complexity of this code is O(m*n logn), since m is constant which is no more than 12, we can say the complexity is bounded by the complexity of merge sort which is O(nlogn). At each recursive call, the function performs two loops, one before the merge sort and another after it and they both have complexity of O(m). The merge sort has a time complexity of O(nlog n).

Therefore, the total time complexity would be m * (2m + n * log n) which is O(m * (m + n * log n))= O(m^2) + O(mnlogn)

Upvotes: 0

Related Questions