What is complexity of T(n) = 2T(n/2) + C, using recurrence equations?
If you draw the recursion tree, you find constants at every level.
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.