What is the worst case time complexity of the following code :

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

NOTE: This question involves recursion which will be explained later in topicBacktracking. So, if you are not able to approach this question now, you can give it a try later.

- Solution Approach
- Complete Solution

35193 successful submissions.