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 time complexity analysis of recursion is critical to understand these approaches and improving our code's efficiency.
Sometimes programmers find it challenging to analyze recursive algorithms due to their mathematical details. But working with recursive algorithms becomes easy when we understand recursive patterns and methods used in the analysis. Without delaying further, let's learn fundamental concepts related to recursion time complexity.
A recurrence relation is an equation describing a sequence where any term is defined using its previous terms. We use recurrence relation to analyze recursive function time complexity in terms of input size.
In the case of recursion, we solve a problem using the solution of smaller subproblems. If time complexity of recursive function is T(n), then time complexity of smaller sub-problems will be defined by the same function but in terms of subproblems input size.
Here is a common approach to writing 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
The above formula provides an approach to define recurrence relation of every recursive algorithm. Then, we solve this recurrence relation and calculate the overall time complexity for recursion in terms of Big-O notation. Let's understand this better via examples of various recurrence relations of popular recursive algorithms.
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 n size array by swapping the first and last values and recursively solving remaining subproblem of reversing (n - 2) size array. At each step of recursion, input size is decreasing by 2.
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 problem of n size using the solution of one subproblem of input size n/2 (Based on comparison, either left or right sub-problem)
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
In merge sort, we are solving problem of n size by using solution of two equal subproblems of input size n/2 and merging sub-problems solution in O(n) time.
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 quick sort, we are dividing array in O(n) time and recursively solving two subproblems of different sizes. The size of the subproblems depends on the choice of pivot in partition algorithm. Suppose after the partition, i elements are in the left subarray (left of the pivot), and n - i - 1 elements are in the right subarray (right of the pivot). Size of the left subproblem = i, Size of the right subproblem = n - i - 1.
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
For finding nth Fibonacci, we are recursively solving and adding two sub-problems of size (n - 1) and (n - 2). Both subproblems are dependent on each other because the value of (n - 1)th Fibonacci depends on the value of (n - 2)th Fibonacci, and so on. Such type of dependent subproblems arises in case of optimization problems in dynamic programming.
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.
A recursion tree is a tree diagram of recursive calls, where each tree node represents the cost of a certain subproblem. The idea would be simple! Time complexity of recursion depends on two factors: 1) Total number of recursive calls and 2) Time complexity of additional operations for each recursive call.
So recursion tree is a diagram representing additional cost for each recursive call in terms of their input size. We should add extra cost for each recursive call to get the overall time complexity. Note: One of the best ideas would be to perform this cost sum level by level.
Merge sort recurrence relation: T(n) = 2T(n/2) + cn, T(1) = c
We are dividing problem of size n into two different subarrays (sub-problems) of size n/2. Here cn represents cost of merging solution of smaller sub-problems (smaller sorted arrays of size n/2). So, at each step of recursion, problem will be divided in half until the size of sub-problem becomes 1.
Here, recursion tree is a full binary tree structure where each node has two children, and each level is completely full. At each level, input size decreases by the factor of 2, and recursion tree will terminate at input size 1. So the height of recursion tree h = logn (Think!)
To explore further, understand the analysis of binary search and quick sort using recursion tree method.
We use the master method for finding time complexity of divide and conquer algorithm that partition 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 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 analysis using the master theorem:
Comparing with master theorem relation with binary search recurrence relation:
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)
Comparing master theorem recurrence with merge sort recurrence relation:
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)
Comparing master theorem recurrence with finding max and min recurrence relation:
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)
Comparing master theorem recurrence with strassen’s multiplication recurrence:
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.8)
Enjoy learning, Enjoy coding, Enjoy algorithms!
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.