Here we first describe Basis condition T(1)=1 (first element is our search element and we are doing constant work)
Now return
recSearch(arr, l+1, r, x) : This line tell us that if element is not at postilion "l" find at l+1
so T(2)=T(1)+1 (here we are adding +1 because of 2 if statement which require negligible amount of time )
so T(k)=T(k-1)+1 where k is our search element
so let take an small example and see how much time it requires let element at position 3rd be our search element
T(2)=T(1)+1
T(3)=T(2)+1
so T(3)=T(1)+1+1 substituting T(2) from previous equation
T(3)=1+1+1=3
so T(k)=k
"if( r < L )" it ensure that we are not searching within bound of array and it is also terminating condition.
so if element is not in array then last search would be n<n which is false, now L will be incremented by 1 so n<n+1 True return -1;
So recurrence relation is T(n) =T(n-1)+1, T(1)=1
space complexity is size of array = n size of L,R,x= Constant so O(n+c)=O(n)
Time complexity: Best case O(1) Average case O(n/2)=O(n) and Worst Case O(n)
Finding Time complexity
T(n)=T(n-1)+1
T(n-1)=T(n-2)+1
Substuting it back in T(n)
T(n)=T(n-1)+1+1
so on T(n)=T(n-(n-1))+1+1..n-1 Times (n-1 times because we have already taken T(1) so form 2 to n it will be n-1)
T(n)=T(1)+ (n-1)*1
T(n)=1+n-1 =n
T(n) =O(n)