Worst case time complexity for the code

Question

Why is the worst time complexity of the following code is O(N)?

/* 
* 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

What's the worst case? the worst case will be that all element are the same and equals to k. Then you have to at least read all elements, which is N. Since most function calls increase the output by 1, there are about N function calls (some returns 0, but they don't spawn new calls). Therefore, the worst time complexity is O(N).