#
4.2. Approaches for Recursive Formulation
In
#
4.2.1. Top Down Approach
- T(i,j) = T(i-1,j) + T(i, j-1) + C \cdot (2i + j) for i,j \geq 1
- T(i,0) = T(0,j) = 1 for i,j \geq 0
- Easily becomes exponential!
#
4.2.2. Bottom Up Approach
- T(i,j) = T(i-1,j) + T(i, j-1) + C \cdot (2i + j) for i,j \geq 1
- T(i,0) = T(0,j) = 1 for i,j \geq 0
- Often much more efficient!
#
4.2.3. Examples
#
4.2.3.1. [ex1] World Series Odds
- Problem
- Dodgers and Yankees are playing the World Series in which either team needs to win n games first.
- Suppose that each team has a $50%$chance of winning any game.
- Let P(i,j) be the probability that if Dodgers needs i games to win, and Yankees needs j games, Dodgers will eventually win the Series.
- Ex: P(2, 3) = \frac {11}{16}
- Compute P(i,j) 0 \leq i,j \leq n \forall n
#
4.2.3.2. [Worse] A Divide-and-Conquer Approach
Recursive formulation
- $P(i,j) $
- \\ = 1 if i=0, j>0
- \\ = 0 if i=0, j=0
- \\ = \frac{P(i-1,j)+P(i,j-1)}{2} if i>0, j>0
If we solve this recurrence relation in the divide-and-conquer way,
- Let T(n) be the maximum time taken by a call to P(i),where i+j =n.
- Then we can prove that T(n) is exponential!
- T(1)=1, T(n) = 2T(n-1) + c \rightarrow O(2^n)
What is the problem of this approach?
#
4.3.2.3. [Better] A Dynamic Programming Approach
- Instead of computing the same repeatedly, fill in a table as suggested below:
- Time Complexity
- For input size (m, n), computing P(m, n) takes O(mn)-time.
- By far better than the Divide-and-Conquer approach.
