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!
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.
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.
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).
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).
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.
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.
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.
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 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.
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.
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.
To explore further, you can understand the analysis of binary search and quicksort using the recursion tree method.
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)
Comparing master theorem recurrence 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.81).
If you have any queries or feedback, please write to us at contact@enjoyalgorithms.com. Enjoy learning, enjoy coding, and enjoy algorithms!
Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.
©2023 Code Algorithms Pvt. Ltd.
All rights reserved.