How to formulate Mathematical equation for 'time complexity' of Searching an integer x in Linked List Using Recursion. Recursive Equation should obviously be in terms of n (where n=total number of elements in linked list). Below is the Java implementation of Recursive Search in Linked list.

public static int search(Node head, int x) {
  if(head==null)
    return -1;
  else if(head.data==x)
     return 1;
  else {
     int res=search(head.next,x);
     if(res==-1)
        return -1;
     else 
        return res 1;
  }
}

I know that time complexity is obviously O(n) as it traverses every element to search in worst case but I want to derive the same from recursive equation.

CodePudding user response：

Define