#Algorithms Solve this recurrence equation only by using Recursion Tree method

Question

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

Comments

https://www.quora.com/What-is-the-complexity-of-T-n-2T-n-2-+-C-using-recurrence-equations

---

I saw that on quora before i posted here and was stuck in this approach, maybe you can explain me the highlighted part?

 

Height of the tree(h)  =  logn

Number of leaves  =   2^h=2^log(n)=n

T(n)=C+2∗C+4∗C+⋯+n∗CT(n)=C+2∗C+4∗C+⋯+n∗C
 

which is same as the number of nodes in the tree. As there are n leaves, we must have n-1 internal nodes. So, the total number of nodes = 2n-1.

so, T(n)=2n−1=O(n).

---

Height of the tree represents number of terms in the series of  total cost(work)

So , c + 2c + 4c + .........lgn terms ... 

c(1+2+4+ .....lgn terms)

c((2^lgn - 1)/(2-1))

c(n-1) 

= O(n)

---

@ankitgupta.1729 Perfect Ankit Bhai. Thanks a lot. :)

 

Answer 1

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 2log2(n)

terms, hence 2log2(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 2log2(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.

Answer 2

use master theorem

according to master theorem f(n) = c, a = 2, b = 2

compare f(n) and n^log a base b

so c , n ^ [log 2 to base 2 is 1]

n is polynomial times greater than c[constant]

so theta(n)

Comments

provide the solution using the recurrence tree method.