次のアルゴリズムの反復関係はなんですか？

Question

漸化関係はT（n）= T（n-1）+ 2 + T（n + 1）以下ですか？
すべてのif文が他のものを排除しているので、変数の代入と最後の行を数えています...このアプローチは正しいですか？

/* 
* V is sorted 
* V.size() = N 
* The function is initially called as searchNumOccurrence(V, k, 0, N-1) 
*/ 
int searchNumOccurrence(vector<int> &V, int k, int start, int end) { 
    if (start > end) return 0; 
    int mid = (start + end)/2; 
    if (V[mid] < k) return searchNumOccurrence(V, k, mid + 1, end); 
    if (V[mid] > k) return searchNumOccurrence(V, k, start, mid - 1); 
    return searchNumOccurrence(V, k, start, mid - 1) + 1 + searchNumOccurrence(V, k, mid + 1, end); 
} 

Answer 1

@GAURANG VYASのコメントに記載されています。再帰関係はT（n）= 2 * T（n/2）+ O（1）であり、Theta（n）である。 Binary SearchはO（log n）にあり、その漸化関係はT（n）= T（n/2）+ O（1）

となりますので、searchNumOccurrence()はすべてのkの出現を検索するので、 Vのすべての要素がkに等しい場合の正規の例。