Apply the recursion tree method to solve the following recurrence: T(n) = 2T(n/2) + 4n

Steps to Solve

1. Identify the Structure of the Recursion Tree

The given recurrence relation is

$$ T(n) = 2T(n/2) + 4n $$

This indicates that at each level of the tree, we have two subproblems of size $n/2$.

2. Calculate the Cost at Each Level

For the root (level 0), the cost is $4n$.
At level 1, each of the two calls to $T(n/2)$ contributes:

$$ 2 \times 4\left(\frac{n}{2}\right) = 4n $$

At level 2, each of the calls to $T(n/4)$ contributes:

$$ 4 \times 4\left(\frac{n}{4}\right) = 4n $$

This pattern continues for each level.

3. Summarize the Costs at Each Level

The cost at each level (0, 1, 2, ...), is consistently $4n$.
If we denote the height of the tree as $h$, then:

• Level 0 contributes: $4n$
• Level 1 contributes: $4n$
• Level 2 contributes: $4n$
• ...
• Level $h$ contributes: $4n$

4. Determine the Height of the Tree

The height of the tree occurs when the problem size reaches the base case (usually $T(1)$).

For the recurrence $T(n) = 2T(n/2)$, the tree reaches a size of 1 when:

$$ \frac{n}{2^h} = 1 $$

Solving this gives:

$$ h = \log_2(n) $$

5. Calculate the Total Cost

The total cost is the sum of costs at all levels. Since there are $h + 1 = \log_2(n) + 1$ levels, the total sum is:

$$ \text{Total Cost} = (h + 1) \times 4n = \left(\log_2(n) + 1\right) \times 4n $$

So, we approximate:

$$ T(n) = 4n \cdot \log_2(n) + 4n $$

6. Final Result Simplification

In big-O notation, we can combine terms to get:

$$ T(n) = O(n \log n) $$