space complexity of this algorithm?

Question

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

Use in last case binary search to find first previous and first next for k element.
Example:
This right part of your vector after you find k:
kkkkkkkkkkkkyyyyyyyyyyyyyyyyyyyy
Didn't need search all k-element with O(n)
You can use binary search O(logn) to find first NoK-element after last k-element.
kkkkkkkkkkkk(y)yyyyyyyyyyyyyyyyyyy

Answer 2

This algorithm will only work on an ordered vector. Use "else if" for readability. O(logn) if no element in vector. O(n) if all element =k. In last case you can use linear search previous and next element !=k instead of using recursion.

Answer 3

yes element will be sorted.how is o(n) can u please elaborate?

Answer 4

You should use best algoritm to find element !=k on the sides of the element k. (This last case)
Linear search isn't best.

Answer 5

aaaabbbccckkkkkkkkkyyyyzzz
m - amount of elements =k
In this example m=9
Your algoritm O(logn+m)

Answer 6

Best algoritm have O(logn + logm)

Answer 7

are u talking about space or time complexity?

Answer 8

Time

Answer 9

ok
what is space complexity of this algorithm?

Answer 10

Only recursion stack
Perhaps
O(logn *m)
logn*m < n

Answer 11

i think it will be o(n) because in the worst case all element will be k and last return statement will be executed always

Answer 12

yes thank u so much for ur time