**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.

**Step1: Count**

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 T** _{n}**
notation.

T** _{n}**: Number of the steps required to solve

T_{1}:
Number of the steps required to solve 1-element problem.

T_{2}:
Number of the steps required to solve 2-element problem.

**Step2: Find Recurrence
Relation**

Recurrence relation is nothing but a simple way of defining T_{n} 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 T_{n}
= T_{n-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:

T_{1} = 1

and when there are 2 elements in the problem, we will need 2 steps

T_{2} = 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

T_{n}
= T_{n-1} +1

and let’s replace
T_{n-1} by using the recurrence
relation T_{n} = T_{n-1} +1

T_{n-1}
= T_{n-2} + 1 (remember, T_{n} = T_{n-1}
+1, so T_{n-1} = T_{n-1-1} +1 is T_{n-1}
= T_{n-2} +1)

then

T_{n}
= T_{n-1} +1= (T_{n-2} +1) +1 = T_{n-2}
+2

Let’s do it
again for T_{n-2}

T_{n-2} = T_{n-3}
+1

then

T_{n}
= T_{n-2} +2= (T_{n-3} +1) +1 = T_{n-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

T_{n}
= T_{n-1} +1

T_{n}
= T_{n-2} +2

T_{n}
= T_{n-3} +3

there is a clear pattern among these 3 equations, and we can write a generic equation for all 3 as follows:

T_{n}
= T_{n-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 T_{n} = T_{n-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 T_{n} = T_{n-k} + k ,
and we need to prove it by expanding it similar to the Step3. We have

T_{n}
= T_{n-k} + k

and on the
right side of this equation, we have T** _{n-k}**
and it is

T** _{n-k}** = T

and let’s
expand T** _{n}** = T

T_{n}
= T_{n-k} + k = (T_{n-k-1} +1) +k = T_{n-k-1} +
k+1

so what? we have

T_{n}
= T_{n-k-1} + k+1

Let’s rewrite it

T_{n}
= T_{n-(k+1)} + (k+1)

add some color

T_{n}
= T_{n-(k+1)} + **(k+1)**

We here
prove that T_{n} = T_{n-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 T _{n }ONLY
in terms of n**

Our goal is now to get rid of the parameter k in T_{n} = T_{n-k} + k so
that we can find a definition of T_{n} 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

T_{1}
= 1

T_{2}
= 2

So, instead
of T_{n-k}, we want to have something like T_{1} or T_{2}
on the right side of the recurrence equation. How can we transform T_{n-k} into T_{1}?

n-k=1

n-1=k

so if k is n-1, we
will have T_{1} on the right:

T_{n}
= T_{n-k} +k

k = n-1

T_{n}
= T_{n-(n-1)} +n - 1

T_{n}
= T_{1} +n - 1

T_{n}
= 1 +n - 1

T_{n}
= 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**