algorithm - クイックソート法によるパーティションの時間計算量の検索

Question

これは、Quicksort の分割アルゴリズムを使用して、n 個の要素の配列で k 番目に小さい数を見つけるアルゴリズムです。

    small(a,i,j,k)
     {
      if(i==j) return(a[i]);
      else
      {
      m=partition(a,i,j);
      if(m==k) return(a[m]);
      else
        {
         if(m>k) small(a,i,m-1,k);
         else small(a,m+1,j,k);
        }     
       }
     }

ここで、i、j は配列の開始インデックスと終了インデックス (ji=n(配列内の要素の数)) であり、k は k 番目に小さい no です。上記のアルゴリズムの最良のケースと平均的なケースは何か、簡単に説明したいと思います。最良の場合、終了条件を計算するべきではないことを知っています。また、パーティションアルゴリズムには O(n) がかかります。漸近的な表記法ではなく、可能であれば正確な数学的結果が必要です。