Сложность времени алгоритма с двумя циклами и двумя рекурсивными вызовами

Question

Вот алгоритм сортировки массива с двумя рекурсивными вызовами. Я попытался рассчитать его временную сложность грубо, но не уверен. Я знаю, что два для циклов будут принимать n + n раз, но что делать с рекурсивными вызовами и как я могу их вычислить? Любой может помочь в вычислении простым математическим способом.

MySort (a[1..n] , n) { 

     If (n <= 2) { 
      If (first element > second) && (n = 2) then do 
       { Interchange a[1] & a[2]; } 
     End if 
     } 
     Else 
     { Assign value to min and max by very first element of array. 
     for (i : = 1 to n) do 
      { If (a[i] > max) then 
       max = a[i]; 
     Else if (a[i] < min) then 
        min = a[i]; //Get max and min element from the array. } 
     End for 
     Calculate MID value of the MAXIMUM & MINIMUM element found. 
     For i : = 1 to n do 
     { 
      If(a[i] < mid) then { Increment Count1 by 1; and P[Count1]=a[i] } 
      Else if (a[i] > mid) then { Increment Count2 by 1; and Q[Count2]=a[i] } 
    //Divide the major array to sub-arrays; 
    //Count1 and Count2 are counters to make check on the size of sub-arrays generated. 
      } 
     End for 
     MySort (P, Count1); 
      MSort (Q, Count2); } 
     End if} 

Answer 1

Существует два цикла, за которыми следуют два рекурсивных вызова. В идеале, каждый вызов сокращал бы половину размера ввода, в результате чего n/2 значения. Это дает рекуррентное соотношение:

T(n) = n + n + T(n/2) + T(n/2) 
T(n) = 2n + 2T(n/2) 

Это соответствует последней строки таблицы, указанной на Master theorem странице:

T(n) = O(nlogn) 

Если вход вход не поровну каждый вызов, то вместо этого принимает п^2 раза, так как размер может быть уменьшен только на 1 каждый звонок:

T(n) = 2n + T(n-1) + T(1) 
T(n) = nT(1) + 2n + 2(n-1) + 2(n-2) + ... 
T(n) = O(n^2)