Question

Solve recurrence step by step T(n) = 2T(n/2)+2n where T(8)=
16

Answer 1

To solve the recurrence relation T(n) = 2T(n/2) + 2n, we can use the recursive tree method and analyze its running time.

Step-by-step explanation:

To solve the recurrence relation T(n) = 2T(n/2) + 2n, we can use the recursive tree method. We start by expanding the recurrence until we reach the base case T(1). We can see that the recurrence has a running time of O(nlogn).

The recursive tree for this recurrence has a height of logn, and at each level, we have 2^n nodes. The work done at each level is 2n, as there are 2n nodes at each level. So, the total work done at each level is 2n * logn, which gives us a total running time of O(nlogn).

Therefore, the solution to the recurrence relation T(n) = 2T(n/2) + 2n is O(nlogn).