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 improve the efficiency of our code.
Sometimes programmers find challenging to analyze recursion due to the mathematical details behind it. But working with recursive algorithms becomes easy when we have a good understanding of recursive patterns and methods used in the analysis. Without delaying further, let's learn fundamental concepts related to the analysis of recursion:
A recurrence relation is an equation that describes a sequence where any term is defined in terms of its previous terms. We use recurrence relation to define and analyse the time complexity of recursive algorithms in terms of input size.
In the case of recursion, we solve the problem using the solution of the smaller subproblems. If the time complexity function of the algorithm is T(n), then the time complexity of the smaller sub-problems will be defined by the same function but in terms of the input size of the subproblems. Here is a common approach to write T(n) if we have k number of subproblems:
T(n) = T(input size of subproblem 1) + T(input size of subproblem 2)....+ T(input size of subproblem k) + Time complexity of additional operations other than recursive calls
The above formula provides an approach to define the recurrence relation of every recursive algorithm. Then, we solve this recurrence relation and calculate the overall time complexity in terms of Big-O notation. Let's understand this better via the 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 the n size array by swapping the first & last value and the recursively solving remaining subproblem of the (n - 2) size array. At each step of recursion, the input size is decreasing by 2.
Decrease by a constant factor: Binary search
binarySearch(A, l, r, k) - if A[mid] = k, return mid - if (A[mid] > k), binarySearch(A, l, mid-1, k) - if (A[mid] < k), binarySearch(A, mid+1, r, k) 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 n size by the solution of one subproblem of input size n/2 (Based on the comparison, either left or right sub-problem)
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
In merge sort, we solve the problem of n size by the solution of two equal subproblems of input size n/2 and merging the solution in O(n) time complexity.
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 quick sort, we are dividing the array in O(n) time and recursively solving two subproblems of different sizes. The size of the subproblems depends on the choice of the pivot in the 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.
Dividing into more than two subproblems of equal size
Dividing into two dependent subproblems: Finding 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
For finding the nth Fibonacci, we are recursively solving and adding the 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 the case of the optimization problems in dynamic programming. We will discuss in detail when we discuss the dynamic programming approach.
Step 1: Identifying input size and smaller subproblems
Step 2: Writing recurrence relation for the time complexity
Step 3: Solving recurrence relation to get the time complexity
We mostly use the following two methods to solve the 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 for the divide and conquers recurrence, but the recursion tree method is always the fundamental approach applied to all the recursive algorithms.
A recursion tree is a tree diagram of recursive calls and the amount of work done at each call. Here each tree node represents the cost of a certain recursive subproblem. The idea would be simple! The time complexity of recursion depends on two factors: 1) Total number of recursive calls 2) Time complexity of additional operations for each recursive call.
So recursion tree is a diagram to represent the additional cost for each recursive call in terms of input size n. To get the overall time complexity, we do a summation of the additional cost for each recursive call. If we calculate the cost of the additional operations at the first level of recursion then we can easily calculate the cost for smaller subproblems.
Steps of analysis using recursion tree method
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 subarrays (sub-problems) of size n/2. Here cn represents the cost of dividing the problem and merging the solution of the smaller sub-problems (smaller sorted arrays of size n/2). Thus, each step of recursion, the problem will be divided in half until the size of the problem becomes 1.
Here, the recursion tree is a complete binary tree structure where each node has two children, and the last level is full. At each level, the input size decreases by the factor of 2, and the recursion tree will terminate at input size 1. So the height of the tree h = logn (Think!)
We use the master method for finding the time complexity of the 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 the 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 subproblems, each of size n/b, where a and b are positive constants. The a subproblems are solved recursively, each in time T(n/b). Here O(n^k) is the cost of dividing the problem and combining the results of the subproblems. There are the three cases of the analysis using the master theorem:
Example 1: Binary search analysis using 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)
Example 2: Merge sort analysis using master theorem
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)
Example 3: Divide and conquer idea of finding max and min
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)
Example 4: Analysis of strassen’s matrix multiplication
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!
Get well-designed application and interview centirc content on ds-algorithms, machine learning, system design and oops. Content will be delivered weekly.