Algorithm Complexity : Recursion Tree

In this post, I aim to explain a method of solving recurrence relations, the result of which will give the complexity of the relation. The performance of the algorithm varies with the input size given to it.

Often counting the number of steps performed by algorithm are used to measure its performance. However, for larger input sizes, this process becomes cumbersome. Also such methods are bound to hardware specifications etc.

The first method we will follow up is Recursion Tree method. A recursion tree for the given recurrence relation is created first. The number of nodes at each level are counted and time taken at the corresponding level is computed. To obtain final result, the time taken at all levels is added up.

The pattern of time computed is observed. Most of the times it is an Arithmetic Progression or a Geometric Progression. The constants are discarded at the end to obtain complexity in terms of input size only. Let us use a simple example deploying the Recursion Tree method.

T(n) = 2 T(n/2) + n2

We start with the non-recurrent value as the root. The expression n2 is non-recurrent here, so it will be the root of our tree.

The next thing is to see the constant value with the recurrent value i.e. T(n/2) here. The constant 2 with it depicts the number of children each node in the tree will have. So the root node will have 2 children here and so on for the subsequent nodes.

drawit-diagram

On adding up time at different levels, we have the expression:
n2 + 2 (n/2)2 + 4 (n/4)2 + ..... + 0
= n2 (1 + 1/2 + 1/4 + ..... + 0)
= n2 (1/(1-1/2))
= n2 (1/(1/2))
= n2 * 2

Now discarding the constant, we have T(n) = O(n2). So the complexity of the recurrence relation is of the order n2 using the recursion tree method.

Leave a Reply

Follow

Get notified with the latest posts

Plugin Supporter WordPress Post Navigation
%d bloggers like this: