algorithm - 查找递归算法的运行时间

Question

我正在尝试查找此算法的运行时（用于查找数组中的第 k 个最小值）：

Select(A[1 . . . n], k) if n ≤ 100 then
  Return the k-th smallest element via brute-force; else
  Divide A into m ← ⌈n/3⌉ consecutive subgroups of size at most 3; 
  for i ← 1 . . . m do
    M[i] ← Median of the i-th subgroup;
  end
  p ← Select(M[1...m],⌊m/2⌋);
  Let B be an array contains all the elements < p in A;
  Let C be an array contains all the elements ≥ p in A;
  if len(B) ≥ k then
    return Select(B,k);
  else
    return Select(C, k − len(B));
  end
end

我试图提出一个递归关系以找到运行时。这就是我认为的：

由于该算法对数组的 n/3 个元素进行递归调用，因此我希望它是 2T(n/3) + O(n)。然后应用大师定理。我是否朝着正确的方向前进？

标签： algorithmrecursionruntimebig-o