Berechnung der Zeitkomplexität von rekursiven Algorithmus T (n) = T (k) + T (nk)

Question

Ich möchte die Zeit Komplexität des folgenden rekursiven Algorithmus berechnen, wo

n = j - i (size of array) 
i ≤ k ≤ j 
process(A, i, j) takes Θ(n) time 

Algo(Array A[], int i, int j) 
    if (i<j) 
     k = process(A, i, j) 
     Algo(A, i, k) 
     Algo(A, k+1, j) 

ich kam mit die folgenden:

Ich bin mir nicht sicher, ob das richtig ist und wenn es ist, wie davon zu gehen?

Update:

Ist das folgende richtig?

Der schlimmste Fall Wert für k i oder j,

T(n) = Θ(n) + T(0) + T(n) 

Answer 1

Diese rekursive Struktur ist eher wie schnell sortieren, deren Worst-Case-Laufzeit ist O(n^2).

algorithm quicksort(A, lo, hi) is 
    if lo < hi then 
     p := partition(A, lo, hi) 
     quicksort(A, lo, p – 1) 
     quicksort(A, p + 1, hi) 

Der Partitionsalgorithmus dauert O(N) Zeit. Für die Analyse wenden Sie sich bitte an Quick-Sort. Ich kann es nicht besser erklären.