CODEWITHSUNDEEP
c++algorithmsearchtime-complexitybinary-search
Divij Jain
Divij Jain

Reputation: 113

What is the time complexity of the following search algorithm?

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

What is the time complexity of this code snippet? I feel like its O(logN) but the correct answer is O(N). Can someone explain clearly why?

Upvotes: 1

Views: 457

Answers (1)

Alberto
Alberto

Reputation: 12949

It's O(N) because if you always take this "branch" (the array contains N elements with value k)

return searchNumOccurrence(V, k, start, mid - 1) + 1 + searchNumOccurrence(V, k, mid + 1, end);

you have to do 2 calls, and you can image it like a complete tree traversal, which is O(N)

Upvotes: 3

Related Questions