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

Posted By on September 18, 2014

Download PDF
Question Bank
Greedy Solution to the Fractional Knapsack Problem

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 2^{log_2 (n)} terms, hence 2^{log_2(n)}*c = cn (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  2^{log_2 (n)} = n. 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.

Question Bank
Greedy Solution to the Fractional Knapsack Problem

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com