algorithm - 以下算法的递归关系是什么？

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);
}

最佳答案

正如@GAURANG VYAS在评论中提到的递推关系为t（n）=2*t（n/2）+o（1），且在θ（n）内。Binary Search在O（log n）中，其递推关系T（n）=T（n/2）+O（1）
由于您的方法searchNumOccurrence()查找给定k的所有匹配项，因此它可以查看V中的所有元素。如果V中的所有元素都等于k，则为规范示例。