# What is complexity of T(n) = 2T(n/2) + C, using recurrence equations?

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

If you draw the recursion tree, you find constants at every level. Height of the tree is log n. It is easy to see that the number of constants at every level is the number of recursvie calls at that level!

Level Constants

n c

n/2,n/2 2c

n/4,n/4,n/4,n/4 4c

Last level will have terms, hence (Note – its log base 2)

This is because for every recursion you have a constant c. (Usually the constants are ignored, but for this case it is easier to see the problem as constants)

So, T(n) = c + 2c + 4c + …… + nc

The above summation can be intimidating initially, until you realize it is the same as the number of nodes in the tree. We now know that there are n leaves . Therefore, we have n-1 internal nodes. So, the total number of nodes in the tree is n+n-1 = 2n-1.

Hence, T(n) = 2n-1 = O(n); the solution using recursion method.