title: Worst case time complexity for the code
body: <p>Why is the worst time complexity of the following code is O(N)?</p>
  
  <pre class="lang-cpp prettyprint-override"><code>/* 
  * V is sorted 
  * V.size() = N
  * The function is initially called as searchNumOccurrence(V, k, 0, N-1)
  */
  
  int searchNumOccurrence(vector&lt;int&gt; &amp;V, int k, int start, int end) {
    if (start &gt; end) return 0;
    int mid = (start + end) / 2;
    if (V[mid] &lt; k) return searchNumOccurrence(V, k, mid + 1, end);
    if (V[mid] &gt; k) return searchNumOccurrence(V, k, start, mid - 1);
    return searchNumOccurrence(V, k, start, mid - 1) + 1 + searchNumOccurrence(V, k, mid + 1, end);
  }
  </code></pre>