計算遞歸算法T（n）的時間複雜度= T（K）+ T（NK）

Question

欲計算以下遞歸算法，其中，

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) 

我想出了的時間複雜度以下內容：

T(n) = Θ(n) + T(k) + T(n-k) 

我不確定這是否正確，如果是這樣，如何繼續？

更新：

是以下是否正確？

對於k的最壞情況值是i或j，

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

Answer 1

這種遞歸結構更像快速排序，其最壞情況下的運行時間爲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) 

分區算法需要O(N)時間。分析請參考Quick-Sort。我無法解釋更好。