I'm trying to get the time complexity of this algorithm but I'm not sure how to. will be glad for any help.
`int g(int arr[], int start, int end, int k)
{
if (start > end) return 0;
int mid = (start + end) / 2;
if (arr[mid] < k) return 1 + g(arr, mid + 2, end, k);
if (arr[mid] > k) return 1 + g(arr, start, mid - 1, k);
return g(arr, start, mid - 1, k) + 1 +
g(arr, mid + 1, end, k);
}`
the answer is O(n).
This is recursion that uses the mechanism of binary search.
Every time we check if arr[mid] is equal to the value k; if it is less than k then we search the right half of the array (the mid+2 should be mid+1), if it is more then we search the left half of the array, if it is equal to k then we search both halves of the array.
So every time we call the recursive function we are only using half the input (half the array).
Thus we can write something like this:
T(n)=2*T(n/2)+1
T(n)=2*2*T(n/(2*2))+1+1
...continue expanding
T(n)=2^k*T(n/(2^k))+k
n/(2^k)=2 ==> k=log(n)
T(n)=2^(log(n))*1+log(n) =
O(n)knowing that 2^log(n)=n using log rules.
even though you didn't ask but the space complexity would be O(log(n)) since the maximum depth of the recursion tree would be log(n).
