Recursion Tree Method for Solving Recurrence Relations

Explanation of the Recursion Tree Method

The recursion tree method is a technique for solving recurrence relations by expanding the recurrence into a tree. Each node represents the cost incurred at a subproblem, and the children of a node represent the recursive subproblems generated. The total cost is found by:

1. Expanding the recurrence into a tree, level by level.
2. Computing the cost contributed at each level.
3. Finding the height (number of levels) of the tree by determining when the subproblem size reaches the base case.
4. Summing the per-level costs across all levels.
5. Expressing the total as a closed form / Big-Oh bound.

Given Data

• Recurrence: $T(n) = 2T(n/2) + 1$ for $n > 1$
• Base case: $T(1) = 1$
• Non-recursive (combine) cost per call: $1$
• Branching factor: $2$, subproblem size scaling: $n/2$

Step 1: Draw the Recursion Tree

Level 0:            T(n)                       cost = 1
                  /      \
Level 1:      T(n/2)    T(n/2)                 cost = 2×1 = 2
             /   \       /   \
Level 2: T(n/4) T(n/4) T(n/4) T(n/4)           cost = 4×1 = 4
                    ...
Level k:  2^k nodes, each of size n/2^k        cost = 2^k

Step 2: Cost at Each Level

Step 3: Height of the Tree

Recursion stops when subproblem size reaches the base case $n/2^k = 1$:

$$2^k = n \implies k = \log_2 n$$

So there are levels $0, 1, \dots, \log_2 n$, i.e. $\log_2 n + 1$ levels.

Note: at the last level, the $2^{\log_2 n} = n$ leaves each have $T(1) = 1$, contributing $n$, which is consistent with the internal-node accounting below.

Step 4: Sum the Total Cost

$$T(n) = \sum_{i=0}^{\log_2 n} 2^i$$

This is a geometric series with ratio $2$:

$$T(n) = \frac{2^{\log_2 n + 1} - 1}{2 - 1} = 2^{\log_2 n + 1} - 1 = 2\cdot 2^{\log_2 n} - 1$$

Since $2^{\log_2 n} = n$:

$$T(n) = 2n - 1$$

Step 5: Big-Oh Notation

$$\boxed{T(n) = 2n - 1 = O(n)}$$

Verification (Master Theorem)

For $T(n)=aT(n/b)+f(n)$ with $a=2,\ b=2,\ f(n)=1=\Theta(n^0)$: $$n^{\log_b a} = n^{\log_2 2} = n^1 = n$$ Since $f(n) = O(n^{1-\varepsilon})$, Case 1 applies, giving $T(n) = \Theta(n^{\log_b a}) = \Theta(n)$. This confirms $O(n)$.

Conclusion

Using the recursion tree method, $T(n) = 2T(n/2) + 1$ solves to $T(n) = 2n - 1 = O(n)$, matching the Master Theorem result.

Optimization Problem and Greedy Strategy

Optimization Problem

An optimization problem is the problem of finding the best solution from all feasible solutions. The goal is either to maximize or minimize some objective function subject to given constraints.

Optimization problems can be divided into two categories:

• Discrete Optimization: Variables are discrete (e.g., integer values). Examples include knapsack problem, shortest path problem, etc.
• Continuous Optimization: Variables are continuous. These include constrained problems and multimodal problems.

Greedy Strategy for Algorithm Design

The greedy strategy (or greedy method) is an algorithmic approach that builds up a solution piece by piece, always choosing the next piece that offers the most immediate or local benefit (the locally optimal choice) at each step, with the hope of finding a global optimum.

Key Idea

At each step, make the choice that looks best at the moment without reconsidering previous choices.

Characteristics of Greedy Strategy

General Steps of Greedy Algorithm

1. Initialize an empty solution set.
2. Select the best available candidate (greedy choice) from the remaining options.
3. Check feasibility: Determine if the selected candidate can be added to the solution without violating constraints.
4. Add the candidate to the solution if feasible.
5. Repeat steps 2-4 until a complete solution is obtained.

Example: Activity Selection Problem

Given a set of activities with start and finish times, select the maximum number of non-overlapping activities.

Greedy Choice: Always select the activity that finishes earliest among the remaining compatible activities.

Activities sorted by finish time:
A1(1,3), A2(2,5), A3(4,6), A4(6,8)

Step 1: Select A1 (earliest finish = 3)
Step 2: A2 overlaps with A1, skip
Step 3: Select A3 (start=4 >= finish of A1=3)
Step 4: Select A4 (start=6 >= finish of A3=6)

Result: {A1, A3, A4} --> Maximum 3 activities

Advantages of Greedy Strategy

• Simple and easy to implement.
• Generally faster than dynamic programming (often O(n log n) or O(n)).
• Works well when greedy choice property and optimal substructure hold.

Limitations

• Does not always produce a globally optimal solution.
• Cannot be applied to all optimization problems (e.g., 0/1 Knapsack does not yield optimal result with greedy).

Common Problems Solved Using Greedy Strategy

• Fractional Knapsack Problem
• Huffman Coding
• Prim's and Kruskal's Minimum Spanning Tree
• Dijkstra's Shortest Path Algorithm
• Activity Selection Problem

In summary, the greedy strategy solves optimization problems by making the locally best choice at each step, which leads to an efficient and often optimal solution when the problem satisfies the greedy choice property and optimal substructure.

Job Sequencing with Deadlines - Greedy Strategy

Problem Statement

Given n jobs, each with a deadline and a profit (earned only if the job is completed by its deadline), find a feasible sequence of jobs that maximizes total profit. Each job takes unit time to complete and only one machine (processor) is available.

Greedy Strategy

The greedy approach selects jobs in decreasing order of profit (most profitable job first) and schedules each job in the latest available time slot before its deadline.

Algorithm

JobSequencingWithDeadline(D, J, n, k)

1. Sort all jobs in decreasing order of profit P.
2. D(0) = J(0) = 0
3. k = 1
4. J(1) = 1        // Select the first (highest profit) job
5. for i = 2 to n do:
      r = k
      while D(J(r)) > D(i) and D(J(r)) ≠ r do:
          r = r - 1
      if D(J(r)) ≤ D(i) and D(i) > r then:
          for l = k downto r+1 do:
              J(l+1) = J(l)
          J(r+1) = i
          k = k + 1
6. Output J(1), J(2), ..., J(k)  // Feasible job sequence with max profit

Step-by-Step Example

After sorting by profit (descending): J1(100), J3(27), J4(25), J2(19), J5(15)

• Select J1 → place at slot 2 → Schedule: [_, J1]
• Select J3 → deadline 2, slot 1 is free → Schedule: [J3, J1]
• Select J4 → deadline 1, slot 1 is taken → skip
• Select J2 → deadline 1, slot 1 is taken → skip
• Select J5 → deadline 3, slot 3 is free → Schedule: [J3, J1, J5]

Result: J3, J1, J5 with total profit = 27 + 100 + 15 = 142

Complexity Analysis

• The outer loop runs n times.
• The inner while loop and shifting loop together run at most O(n) per iteration.
• Therefore, the overall time complexity is:

$$T(n) = O(n^2)$$

The dominant term is the job insertion step, making the overall complexity O(n²).

Summary