How to Compute Time Complexity of Recursive Algorithms
In this tutorial, we will discuss how to compute the time complexity of recursive algorithms in 6 Steps. I assume that you already know what a recursive algorithm is.
Our goal is to find the number of steps required to solve an n-element problem using a recursive algorithm, where n is usually the number of elements in the problem. There are also cases where is actually value of the input. However, in general you can think of n as the size of the problem.
For small n values (e.g., 1, 2, 4, 8), count how many steps you need to solve the problem. Then, describe the number of the steps using the Tn notation.
Tn: Number of the steps required to solve n-element problem.
T1: Number of the steps required to solve 1-element problem.
T2: Number of the steps required to solve 2-element problem.
Step2: Find Recurrence Relation
Recurrence relation is nothing but a simple way of defining Tn recursively. Namely, we try to find an equation that defines the number of the steps required to solve an n-element problem in terms of number of the steps required for solving the same problem with less than n elements. For example, the recurrence relation† Tn = Tn-1 + 1 means if we have 1 more element (n versus n-1), we need one more step (+1). I accept the fact that the term recurrence relation sounds scary, but its meaning is really simple. For example, let us assume that when there is only one element in our problem, we just need 1 step, namely:
T1 = 1
and when there are 2 elements in the problem, we will need 2 steps
T2 = 2
Step3: Expand the Recurrence Relation
Expand the recurrence relation by replacing the term on the right side of the equation using the entire recurrence relation. For example, we start with
Tn = Tn-1 +1
and letís replace Tn-1 by using the recurrence relation Tn = Tn-1 +1
Tn-1 = Tn-2 + 1† (remember, Tn = Tn-1 +1, so Tn-1 = Tn-1-1 +1 is Tn-1 = Tn-2 +1)
Tn = Tn-1 +1= (Tn-2 +1) +1 = Tn-2 +2
Letís do it again for Tn-2
Tn-2 = Tn-3 +1
Tn = Tn-2 +2= (Tn-3 +1) +1 = Tn-3 +3
Step4: Find a Pattern While Expanding the Recurrence Relation
We try to understand how the recurrence relation changes when we expand it.† For example, think of the expansions from the Step3
Tn = Tn-1 +1
Tn = Tn-2 +2
Tn = Tn-3 +3
there is a clear pattern among these 3 equations, and we can write a generic equation for all 3 as follows:
Tn = Tn-k +k
In other words, if we add k elements to our problem, we need k more steps to solve the problem. Please note that this is the case for our example, the recurrence relation Tn = Tn-1 +1. For your problem, it will probably be different.
Step5: Verify the Pattern by Expanding the Recurrence Relation
We claim that the pattern is Tn = Tn-k + k , and we need to prove it by expanding it similar to the Step3. We have
Tn = Tn-k + k
and on the right side of this equation, we have Tn-k and it is
Tn-k = Tn-k-1 +1† (remember that Tn = Tn-1 +1)
and letís expand Tn = Tn-k +k
Tn = Tn-k + k = (Tn-k-1 +1) +k = Tn-k-1 + k+1
so what? we have
Tn = Tn-k-1 + k+1
Letís rewrite it
Tn = Tn-(k+1) + (k+1)
add some color
Tn = Tn-(k+1) + (k+1)
We here prove that Tn = Tn-k + k is also accurate for k+1. In other words, we proved it by mathematical induction. If you need to learn more about the mathematical induction, you can read and study Mathematical Induction Tutorial.
Step6: Write Tn ONLY in terms of n
Our goal is now to get rid of the parameter k in Tn = Tn-k + k so that we can find a definition of Tn only in terms of n. Why do we need such a definition? Because it will tell us how many steps we need to solve a problem when we have n elements. Considering our example, from Step1 and Step2, we know that
T1 = 1††††††††††††††††††
T2 = 2††††††††††††††††††
So, instead of Tn-k, we want to have something like T1 or T2 on the right side of the recurrence equation. How can we transform Tn-k into T1?
so if k is n-1, we will have T1 on the right:
Tn = Tn-k +k
k = n-1
Tn = Tn-(n-1) +n - 1
Tn = T1 +n - 1
Tn = 1 +n - 1
Tn = n
This means that if we have n elements in the problem, we need n steps to solve the problem. Accordingly, we can say that the time complexity of this problem is O(n) .
Please note that you can apply these steps any recursive problem to analyze the time complexity of the problem. To understand it better, you should work on an actual problem, such as Time Complexity of Recursive Factorial Algorithm.
This is the
end of the tutorial. I hope you enjoyed it. Please feel free to contact me at haberdar AT gmail dot
com. You can use anything here as long
as you give credit as follows:
Hakan Haberdar, "How to Compute Time Complexity of Recursive Algorithms", Computer Science Tutorials [online], (Accessed MM-DD-YYYY) Available from: http://www.haberdar.org/time-complexity-recursive-algorithms-tutorial.htm