Time Complexity Analysis of Recursive Function in DSA

Recursion is one of the popular problem-solving approaches in data structure and algorithms. Even some problem-solving approaches are totally based on recursion: Decrease and conquer, Divide and conquer, DFS traversal of tree and graph, Backtracking, Top-down approach of dynamic programming, etc. So learning analysis of recursion is critical to understanding the thought process behind these approaches and improving the code performance.

Sometimes programmers find it challenging to analyze recursion due to its mathematical details. However, working with recursion becomes easy when we understand various patterns of recursive algorithms and methods used in the analysis. So let's start the idea step by step!

What is the recurrence relation of a recursive function?

A recurrence relation is a mathematical equation where any term is defined using its previous terms. We use recurrence relations to analyze the time complexity of recursive algorithms in terms of input size. But the critical question is: How can we write the recurrence relation of a recursive algorithm? Let's think!?

In recursion, we solve a problem by breaking it down into smaller subproblems. If the time complexity function of input size n is T(n), then the time complexity of the smaller subproblems will be defined by the same function, but in terms of the subproblem's input size. So here is an approach to write T(n) if we have k number of subproblems:

T(n) = T(Input size of 1st subproblem) + T(Input size of 2nd subproblem) + .... + T(Input size of kth subproblem) + Time complexity of additional operations other than recursive calls.

We can use the above formula to define the recurrence relation of every recursive function. We then solve this recurrence relation and calculate the overall time complexity in terms of Big-O notation. Let's better understand this via examples of various recurrence relations of popular recursive algorithms.

Decrease by a constant: Reverse an array

reverse (A[], l, r) 
- swap(A[l], A[r]) 
- reverse(A, l + 1, r - 1)
- Base Case: if (l >= r), then return.

We are reversing an n-size array by swapping the first and last values and recursively solving the subproblem of reversing (n - 2) size array. At each step of recursion, the input size decreases by 2.

• Time complexity T(n) = Time complexity of solving an (n - 2) size problem + Time complexity of the swapping operation = T(n - 2) + O(1).
• The recurrence relation => T(n) = T(n - 2) + c, where T(1) = c.

Decrease by a constant factor: Binary search

binarySearch(A[], l, r, target)
- if (A[mid] == target), return mid
- if (A[mid] > target), binarySearch(A, l, mid - 1, target)
- if (A[mid] < target), binarySearch(A, mid + 1, r, target)

Base case: If (l > r), then return -1.

At each step of recursion, we are doing one comparison and decreasing the input size by half. In other words, we are solving the problem of size n using the solution of one subproblem of input size n/2 (based on the comparison, either the left or right sub-problem).

• The time complexity T(n) = Time complexity of the n/2 size problem + Time complexity of the comparison operation = T(n/2) + O(1).
• The recurrence relation of binary search is T(n) = T(n/2) + c, where T(1) = c.

Dividing into two equal size subproblems: Merge sort

mergeSort (A[], l, r)
- mid = l + (r - l)/2
- mergeSort(A, l, mid)
- mergeSort(A, mid + 1, r)
- merge(A, l, mid, r)

Base case: if (l == r), then return.

At each step of recursion, we are doing one comparison and decreasing the input size by half. In other words, we are solving the problem of size n using the solution of one subproblem of input size n/2 (based on the comparison, we are searching in either the left half or right half).

• Time complexity T(n) = Time complexity of n/2 size problem + Time complexity of constant extra operations = T(n/2) + O(1).
• The recurrence relation => T(n) = T(n/2) + c, where T(1) = c.

Dividing into two different size subproblems: Quick sort

quickSort(A[], l, r)
- pivot = partition(A, l, r)
- quickSort(A, l, pivot - 1)
- quickSort(A, pivot + 1, r)

Base case: if (l >= r), then return.

In quicksort, we divide an array into two subarrays in O(n) time using the partition algorithm and recursively sort each subarray. The size of the subarrays depends on the choice of pivot in the partition algorithm. 

Suppose k number of elements are in the left subarray (left of the pivot), and n - k - 1 number of elements are in the right subarray (right of the pivot). So the size of the left subproblem is k, and the size of the right subproblem is n - k - 1.

• Time complexity T(n) = Time complexity of the partition algorithm + Time complexity of the left sub-problem of size k + Time complexity of the right sub-problem of size (n - k - 1) = O(n) + T(k) + T(n - k - 1) = T(k) + T(n - k - 1) + cn.
• The recurrence relation => T(n) = T(k) + T(n - k - 1) + cn, where T(1) = c.

Dividing into more than two subproblems of equal size

Karatsuba algorithm for fast multiplication: Here, we solve the integer multiplication problem of size n bits using three sub-problems of size n/2 bits and combine these solutions in O(n) time. Recurrence relation: T(n) = 3T(n/2) + cn, where T(1) = c.

Strassen’s matrix multiplication: Here, we solve the matrix multiplication problem of size n using the solution of seven sub-problems of size n/2 and combining these solutions in O(n^2) time. Recurrence relation: T(n) = 7T(n/2) + cn^2, where T(1) = c.

Dividing into two dependent subproblems: Finding the nth Fibonacci

fib (n) = fib (n - 1) + fib (n - 2)
Base case: if (n <= 1), return n 
Here we have 2 base cases: fib(0) = 0 and fib(1) = 1.

To find the nth Fibonacci number, we recursively solve and add two subproblems of size (n - 1) and (n - 2). Here subproblems are dependent on each other because the value of the nth Fibonacci depends on the (n - 1)th and (n - 2)th Fibonacci, and the value of the (n - 1)th Fibonacci depends on the value of the (n - 2)th Fibonacci, and so on. Such types of dependent subproblems arise in dynamic programming problems.

• Time complexity T(n) = Time complexity of finding the (n - 1)th Fibonacci + Time complexity of finding the (n - 2)th Fibonacci + Time complexity of addition operation = T(n - 1) + T(n - 2) + O(1).
• Recurrence relation of finding the nth Fibonacci number: T(n) = T(n - 1) + T(n - 2) + c, where T(n) = c for n <= 1.

Steps to analyse the time complexity of recursive algorithms

Step 1: Identify input size and smaller subproblems

• We first identify the input size of the larger problem.
• Then we recognise the total number of smaller sub-problems.
• Finally, we identify the input size of smaller sub-problems.

Step 2: Write the recurrence relation for the time complexity

• We define the time complexity function for the larger problem in terms of the input size. For example, if the input size is n, then the time complexity function would be T(n).
• Then we define the time complexity of smaller subproblems. For example, in the case of merge sort, the input size of both subproblems is n/2 each, so the time complexity of each subproblem would be T(n/2).
• Next, we analyze the worst-case time complexity of additional operations. For example, in merge sort, the divide (O(1)) and merging process (O(n)) are extra operations.
• We add the time complexities of the sub-problems and additional operations to get the equation of the overall time complexity function T(n).
• We also define the time complexity of the base case, i.e., the smallest version of the problem. Our solution to the recurrence depends on this, so we need to define it correctly. Think!

Step 3: Solving recurrence relation to get the time complexity

We mainly use the following two methods to solve recurrence relations in algorithms and data structure. We can choose these methods depending on the nature of the recurrence relation. The master method works best to analyse divide and conquer algorithms, but a recursion tree method is always a fundamental approach applied to all types of recursive algorithms.

• Method 1: Recursion Tree Method
• Method 2: Master Theorem

Method 1: Analysis of recursion using Recursion Tree Method

A recursion tree is a tree diagram of recursive calls where each tree node represents the cost of a certain subproblem. The idea is simple! The time complexity of a recursive function depends on two factors: 1) the total number of recursive calls and 2) the time complexity of additional operations for each recursive call.

So, a recursion tree is a diagram that represents the additional cost for each recursive call in terms of its input size. We should add the extra cost for each recursive call to get the overall time complexity. The best idea is to perform this sum of extra cost level by level.

Steps of recursion analysis using the recursion tree method

• Draw the recursion tree for the given recurrence relation.
• Calculate the cost of additional operations for each recursive call.
• Now calculate the cost of additional operations at each level by adding the cost of each node present at that level.
• Finally, add the cost of each level to determine the total cost of recursion. Simplify this expression to get the overall time complexity recursion in terms of big-O notation.

Example: Analysis of merge sort using recursion tree method

Merge sort recurrence relation: T(n) = 2T(n/2) + cn, T(1) = c.

We are dividing the problem of size n into two different sub-problems of size n/2. Here cn represents the extra cost of merging the solution of two smaller sub-problems of size n/2 (merging two smaller sorted arrays of size n/2). One more thing: At each step of recursion, the problem will be divided in half until the size of the sub-problem becomes 1. 

1. We start with the term cn as the root, which represents the cost of additional operations at the first level of the recursion tree. The left and right children of the root are the time complexities of the two smaller sub-problems, which are T(n/2). Now we move one level further by expanding T(n/2).
2. At the second level, there are two nodes of size n/2, and the cost of the additional operations at each node is cn/2. So the overall cost of additional operations at the second level of recursion is cn/2 + cn/2 = cn.
3. Similarly, we move to the third level where we have 4 nodes of size n/4, and the cost of the additional operations at each node is cn/4. The total cost at the third level is cn/4 + cn/4 + cn/4 + cn/4 = cn.
4. In a similar way, we continue expanding each internal node in the recursion tree until the problem sizes get down to 1. The bottom level has n nodes, each contributing a cost of c. So the total cost at the last level is cn.
5. In general, level i has 2^i nodes, each contributing a cost of cn/2^i. So the total cost of any ith level is 2^i *(cn/2^i) = cn.

Here, the recursion tree is a full binary tree structure where each node has two children, and each level is completely full. At each level, the input size decreases by a factor of 2, and the recursion tree will terminate at an input size of 1. So the height of the recursion tree h = logn.

• The total number of levels in a binary tree = height of the binary tree + 1 = logn + 1.
• To compute the total cost represented by the recurrence, we add up the costs of all the levels. The recursion tree has logn + 1 levels, each costing cn. So the total cost = cn * (logn + 1) = cnlogn + cn.
• After ignoring the low-order term and the constant c in (cnlogn + cn), the time complexity of merge sort = O(nlogn).

To explore further, you can understand the analysis of binary search and quicksort using the recursion tree method.

Method 2: Analysis of Recursion using Master Theorem

We use the master method for finding the time complexity of the divide and conquer algorithm that partitions an input into smaller subproblems of equal sizes. It is primarily a direct way to get the solution for recurrences that can be transformed to the type: T(n) = aT(n/b) + O(n^k), where a≥1 and b>1.

The master theorem recurrence describes the time complexity of an algorithm that divides a problem of size n into a number of subproblems, each of size n/b, where a and b are positive constants. Here a number of subproblems are solved recursively, each in time T(n/b) and O(n^k) is the cost of dividing the problem and combining the solution of subproblems.

There are three cases of recursion analysis using the master theorem:

Case 1: When k < logb(a) then T(n) = O(n^logb(a))

Case 2: When k = logb(a) then T(n) = O(n^k * logn)

Case 3: When k > logb(a) then T(n) = O(n^k)

Special notes

• The general recurrence relation of the master theorem is T(n) = aT(n/b) + f(n), where f(n) is an asymptotically positive function. For simplicity of analysis, we assume that f(n) = O(n^k) for some positive constant k. This assumption holds true for most recursive solutions, where the cost of the additional operations is polynomial in n.
• The master theorem is derived from the recursion tree method, where the height of the recursion tree is logb(n). However, the mathematical proof of this theorem is beyond the scope of this discussion. If you are interested in learning the proof, you can refer to the CLRS book.

Example 1: Binary search analysis using master theorem

Comparing master theorem recurrence relation with binary search recurrence relation:

• T(n) = aT(n/b) + O(n^k)
• T(n) = T(n/2) + c

Here a = 1, b = 2 (a > 1 and b > 1)
k = 0 because n^k = c = Cn^0

=> logb(a) = log2(1) = 0
=> k = logb(a)

We can apply case 2 of the master theorem.

T(n) = O(n^k * log(n)) = O(n^0 * log(n)) = O(logn).

Example 2: Merge sort analysis using master theorem

Comparing master theorem recurrence with merge sort recurrence relation:

• T(n) = aT(n/b) + O(n^k)
• T(n) = 2 T(n/2) + cn

Here a = 2, b = 2 (a > 1 and b > 1)
O(n^k)= cn = O(n¹) => k = 1

logb(a) = log 2(2) = 1
Hence => k = logb(a) = 1

We can apply case 2 of the master theorem.

Time complexity T(n) = O(n^k * logn) = O(n^1 * logn) = O(nlogn).

Example 3: Divide and conquer idea of finding max and min

Comparing master theorem recurrence with finding max and min recurrence relation:

• T(n) = aT(n/b) + O(n^k)
• T(n) = 2 T(n/2) + c

Here a = 2, b = 2 (a > 1 and b > 1)
O(n^k)= cn = O(n^0) => k = 0

logb(a) = log 2(2) = 1
Hence => logb(a) > k

We can apply case 1 of the master theorem.

Time complexity T(n) = O(n^logb(a)) = O(n^1) = O(n).

Example 4: Analysis of Strassen’s matrix multiplication

Comparing master theorem recurrence with Strassen’s multiplication recurrence:

• T(n) = aT(n/b) + O(n^k)
• T(n) = 7T(n/2) + cn^2

Here a = 7, b = 2 (a > 1 and b > 1)
O(n^k)= cn^2 = O(n^2) => k = 2

logb(a) = log 2(7) = 2.8 (Approximately)
Hence => logb(a) > k

so we can apply case 1 of the master theorem.

Time complexity T(n) = O(n^logb(a)) = O(n^log2(7)) = O(n^2.81).

Explore analysis of following recursive algorithms

• Finding the max element in an array recursively: T(n) = T(n - 1) + O(1).
• Recursive insertion sort: T(n) = T(n - 1) + O(n).
• Tower of Hanoi puzzle: T(n) = 2T(n - 1) + O(1).
• Finding the closest pair of points: T(n) = 2T(n/2) + O(nlogn).
• Divide and conquer algorithm of the max subarray sum: T(n) = 2T(n/2) + O(n).
• Divide and conquer algorithm of finding the majority element: T(n) = 2T(n/2) + O(n).
• Recursively searching in a balanced BST: T(n) = T(n/2) + O(1)
• DFS traversal of a binary tree: T(n) = T(i) + T(n - i - 1) + O(1), where i is the number of nodes in the left subtree and (n - i - 1) is the number of nodes in the right subtree.
• Average case analysis of the quick-select algorithm for finding the kth smallest element: T(n) = 2/n * (i = n/2 to n-1 ∑ T(i)) + cn.
• Brute force recursive algorithm of the longest common subsequence: T(n, m) = T(n-1, m-1) + O(1), if the last values of the strings are equal, otherwise T(n, m) = T(n-1, m) + T(n, m-1) + O(1).
• Recurrence relation to count the number of unique binary search trees with n keys (Catalan number): T(n) = Σ (i = 1 to n) [T(i - 1) * T(n - i)].

If you have any queries or feedback, please write to us at contact@enjoyalgorithms.com. Enjoy learning, enjoy coding, and enjoy algorithms!