writing reccurrence equation

Question

linear search recursive program 

int recSearch(int arr[], int l, int r, int x)

{

     if (r < l)

        return -1;

     if (arr[l] == x)

        return l;

     return recSearch(arr, l+1, r, x);

}

how will you write reccurrence equation to find time complexity of it 

Comments

either space or time complexity does not matter on what the program is for, it depends on how you are implementing it..

space complexity= space required other than provided input + depth of recursion tree.

here depth of recursion tree=O(r-l) and extra space required other than input=O(1)

therefore space complexity=O(r-l) + O(1)= O(r-l)

---

bhai ye to smjh gya ki kese aya #recursion tree bnaya ha bhut programs ka but here input ni dia , to tum dummy data leke krte ho build recursion tree or other approach ? plz tell

---

T(l) = T(l+1) + 1, l<r

      = 1, l>=r      // here  i think condition should be only l>r  , if (r < l ) it will execute only when l>r)

Answer 1

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)

Comments

sir  , means

it will be,

T(l) = T(l+1) + 1, l<r

      = 1, l>=r

and complexity will be O(r-l)  , its wrong ?

---

l and r are pointers we are maintaining

l is used to determine current position and r is used to determine last position

now suppose we have array of 10 elements and our desired element is at location 7 so as per your complexity analysis O(10-1)= O(9) will be answer but in reality it is O(7)

we can re write is as

T(n) = $\left\{\begin{matrix} 1 & n=1 \\ T(n-1)+1 & n>1 \end{matrix}\right.$

---

thanks sir