How to find time complexity of recursive function

To analyze the time complexity of a recursive function, you can follow these steps:

1. Determine the recurrence relation: Identify the recursive calls and their respective inputs. Write an equation that expresses the time complexity of the function in terms of its inputs.
2. Solve the recurrence relation: Solve the equation to get a closed-form solution for the time complexity.
3. Analyze the solution: Determine the dominant term(s) in the closed-form solution to get the time complexity of the function.

Let’s take an example of a recursive function to see how to apply these steps:

int factorial(int n) { 
  if (n == 0) { 
      return 1; 
    } else { 
      return n * factorial(n - 1); 
  } 
}

1. Determine the recurrence relation: In this function, we have one recursive call with input n - 1. Therefore, we can write the recurrence relation as follows:

T(n) = T(n-1) + O(1)

where T(n) is the time complexity of the function for input n and O(1) represents the constant time taken for the base case.

1. Solve the recurrence relation: To solve the recurrence relation, we can use the iterative method, which involves expanding the equation until we reach the base case:

T(n) = T(n-1) + O(1) 
     = T(n-2) + O(1) + O(1) 
     = T(n-3) + O(1) + O(1) + O(1) 
     = ... 
     = T(0) + O(1) + O(1) + ... + O(1)