4.4 The recursion-tree method for solving recurrences

4.4-1

Use a recursion tree to determine a good asymptotic upper bound on the recurrence \(T(n) = 3T(\lfloor n / 2 \rfloor) + n\). Use the substitution method to verify your answer.

• The subproblem size for a node at depth \(i\) is \(n / 2^i\).

  Thus, the tree has \(\lg n + 1\) levels and \(3^{\lg n} = n^{\lg 3}\) leaves.

  The total cost over all nodes at depth \(i\), for \(i = 0, 1, 2, \ldots, \lg n - 1\), is \(3^i(n / 2^i) = (3 / 2)^i n\).

  \[ \begin{aligned} T(n) & = n + \frac{3}{2}n + \Big(\frac{3}{2}\Big)^2 n + \cdots + \Big(\frac{3}{2}\Big)^{\lg n - 1} n + \Theta(n^{\lg 3}) \\\\ & = \sum_{i = 0}^{\lg n - 1} \Big(\frac{3}{2}\Big)^i n + \Theta(n^{\lg 3}) \\\\ & = \frac{(3 / 2)^{\lg n} - 1}{(3 / 2) - 1}n + \Theta(n^{\lg 3}) \\\\ & = 2[(3 / 2)^{\lg n} - 1]n + \Theta(n^{\lg 3}) \\\\ & = 2[n^{\lg(3 / 2)} - 1]n + \Theta(n^{\lg 3}) \\\\ & = 2[n^{\lg 3 - \lg 2} - 1]n + \Theta(n^{\lg 3}) \\\\ & = 2[n^{\lg 3 - 1 + 1} - n] + \Theta(n^{\lg 3}) \\\\ & = O(n^{\lg 3}). \end{aligned} \]

• We guess \(T(n) \le cn^{\lg 3} - dn\),

  \[ \begin{aligned} T(n) & = 3T(\lfloor n / 2 \rfloor) + n \\\\ & \le 3 \cdot (c(n / 2)^{\lg 3} - d(n / 2)) + n \\\\ & = (3 / 2^{\lg 3})cn^{\lg 3} - (3d / 2)n + n \\\\ & = cn^{\lg 3} + (1 - 3d / 2)n, \end{aligned} \]

  where the last step holds for \(d \ge 2\).

4.4-2

Use a recursion tree to determine a good asymptotic upper bound on the recurrence \(T(n) = T(n / 2) + n^2\). Use the substitution method to verify your answer.

• The subproblem size for a node at depth \(i\) is \(n / 2^i\).

  Thus, the tree has \(\lg n + 1\) levels and \(1^{\lg n} = 1\) leaf.

  The total cost over all nodes at depth \(i\), for \(i = 0, 1, 2, \ldots, \lg{n - 1}\), is \(1^i (n / 2^i)^2 = (1 / 4)^i n^2\).

  \[ \begin{aligned} T(n) & = \sum_{i = 0}^{\lg n - 1} \Big(\frac{1}{4}\Big)^i n^2 + \Theta(1) \\\\ & < \sum_{i = 0}^\infty \Big(\frac{1}{4}\Big)^i n^2 + \Theta(1) \\\\ & = \frac{1}{1 - (1 / 4)} n^2 + \Theta(1) \\\\ & = \Theta(n^2). \end{aligned} \]

• We guess \(T(n) \le cn^2\),

  \[ \begin{aligned} T(n) & \le c(n / 2)^2 + n^2 \\\\ & = cn^2 / 4 + n^2 \\\\ & = (c / 4 + 1)n^2 \\\\ & \le cn^2, \end{aligned} \]

  where the last step holds for \(c \ge 4 / 3\).

4.4-3

Use a recursion tree to determine a good asymptotic upper bound on the recurrence \(T(n) = 4T(n / 2 + 2) + n\). Use the substitution method to verify your answer.

• The subproblem size for a node at depth \(i\) is \(n / 2^i\).

  Thus, the tree has \(\lg n + 1\) levels and \(4^{\lg n} = n^2\) leaves.

  The total cost over all nodes at depth \(i\), for \(i = 0, 1, 2, \ldots, \lg n - 1\), is \(4^i(n / 2^i + 2) = 2^i n + 2 \cdot 4^i\).

  \[ \begin{aligned} T(n) & = \sum_{i = 0}^{\lg n - 1} (2^i n + 2 \cdot 4^i) + \Theta(n^2) \\\\ & = \sum_{i = 0}^{\lg n - 1} 2^i n + \sum_{i = 0}^{\lg n - 1} 2 \cdot 4^i + \Theta(n^2) \\\\ & = \frac{2^{\lg n} - 1}{2 - 1}n + 2 \cdot \frac{4^{\lg n} - 1}{4 - 1} + \Theta(n^2) \\\\ & = (2^{\lg n} - 1)n + \frac{2}{3} (4^{\lg n} - 1) + \Theta(n^2) \\\\ & = (n - 1)n + \frac{2}{3}(n^2 - 1) + \Theta(n^2) \\\\ & = \Theta(n^2). \end{aligned} \]

• We guess \(T(n) \le c(n^2 - dn)\),

  \[ \begin{aligned} T(n) & = 4T(n / 2 + 2) + n \\\\ & \le 4c[(n / 2 + 2)^2 - d(n / 2 + 2)] + n \\\\ & = 4c(n^2 / 4 + 2n + 4 - dn / 2 - 2d) + n \\\\ & = cn^2 + 8cn + 16c - 2cdn - 8cd + n \\\\ & = cn^2 - cdn + 8cn + 16c - cdn - 8cd + n \\\\ & = c(n^2 - dn) - (cd - 8c - 1)n - (d - 2) \cdot 8c \\\\ & \le c(n^2 - dn), \end{aligned} \]

  where the last step holds for \(cd - 8c - 1 \ge 0\).

4.4-4

Use a recursion tree to determine a good asymptotic upper bound on the recurrence \(T(n) = 2T(n - 1) + 1\). Use the substitution method to verify your answer.

• The subproblem size for a node at depth \(i\) is \(n - i\).

  Thus, the tree has \(n + 1\) levels (\(i = 0, 1, 2, \dots, n\)) and \(2^n\) leaves.

  The total cost over all nodes at depth \(i\), for \(i = 0, 1, 2, \ldots, n - 1\), is \(2^i\).

  The \(n\)-th level has \(2^n\) leaves each with cost \(\Theta(1)\), so the total cost of the \(n\)-th level is \(\Theta(2^n)\).

  Adding the costs of all the levels of the recursion tree we get the following:

  \[ \begin{aligned} T(n) & = \sum_{i = 0}^{n - 1} 2^i + \Theta(2^n)\\\\ & = \frac{2^n - 1}{2 - 1} + \Theta(2^n)\\\\ & = 2^n - 1 + \Theta(2^n)\\\\ & = \Theta(2^n). \end{aligned} \]

• We guess \(T(n) \le c2^n - d\),

  \[ \begin{aligned} T(n) & \le 2(c2^{n - 1} - d) + 1 \\\\ & = c2^n - 2d + 1 \\\\ & \le c2^n - d \end{aligned} \]

  Where the last step holds for \(d \ge 1\). Thus \(T(n) = O(n^2)\).

4.4-5

Use a recursion tree to determine a good asymptotic upper bound on the recurrence \(T(n) = T(n - 1) + T(n / 2) + n\). Use the substitution method to verify your answer.

This is a curious one. The tree makes it look like it is exponential in the worst case. The tree is not full (not a complete binary tree of height \(n\)), but it is not polynomial either. It's easy to show \(O(2^n)\) and \(\Omega(n^2)\).

To justify that this is a pretty tight upper bound, we'll show that we can't have any other choice. If we have that \(T(n) \le cn^k\), when we substitue into the recurrence, the new coefficient for \(n^k\) can be as high as \(c(1 + \frac{1}{2^k})\) which is bigger than \(c\) regardless of how we choose the value \(c\).

• We guess \(T(n) \le c2^n - 4n\),

  \[ \begin{aligned} T(n) & \le c2^{n - 1} - 4(n - 1) + c2^{n / 2} - 4n / 2 + n \\\\ & = c(2^{n - 1} + 2^{n / 2}) - 5n + 4 & (n \ge 1 / 4) \\\\ & \le c(2^{n - 1} + 2^{n / 2}) - 4n & (n \ge 2)\\\\ & = c(2^{n - 1} + 2^{n - 1}) - 4n \\\\ & \le c2^n - 4n \\\\ & = O(2^n). \end{aligned} \]

• We guess \(T(n) \ge cn^2\),

  \[ \begin{aligned} T(n) & \ge c(n - 1)^2 + c(n / 2)^2 + n \\\\ & = cn^2 - 2cn + c + cn^2 / 4 + n \\\\ & = (5 / 4)cn^2 + (1 - 2c)n + c \\\\ & \ge cn^2 + (1 - 2c)n + c & (c \le 1 / 2) \\\\ & \ge cn^2 \\\\ & = \Omega(n^2). \end{aligned} \]

4.4-6

Argue that the solution to the recurrence \(T(n) = T(n / 3) + T(2n / 3) + cn\), where \(c\) is a constant, is \(\Omega(n\lg n)\) by appealing to the recursion tree.

We know that the cost at each level of the tree is \(cn\) by examining the tree in figure 4.6. To find a lower bound on the cost of the algorithm, we need a lower bound on the height of the tree.

The shortest simple path from root to leaf is found by following the leftest child at each node. Since we divide by \(3\) at each step, we see that this path has length \(\log_3 n\). Therefore, the cost of the algorithm is

4.4-7

Draw the recursion tree for \(T(n) = 4T(\lfloor n / 2 \rfloor) + cn\), where \(c\) is a constant, and provide a tight asymptotic bound on its solution. Verify your answer with the substitution method.

• The subproblem size for a node at depth \(i\) is \(n / 2^i\).

  Thus, the tree has \(\lg n + 1\) levels and \(4^{\lg n} = n^{\lg 4} = n^2\) leaves.

  The total cost over all nodes at depth \(i\), for \(i = 0, 1, 2, \ldots, \lg n - 1\), is \(4^i(cn / 2^i) = 2^icn\).

  \[ \begin{aligned} T(n) & = \sum_{i = 0}^{\lg n - 1} 2^icn + \Theta(n^2) \\\\ & = \frac{2^{\lg n} - 1}{2 - 1}cn + \Theta(n^2) \\\\ & = \Theta(n^2). \end{aligned} \]

• For \(O(n^2)\), we guess \(T(n) \le dn^2 - cn\),

  \[ \begin{aligned} T(n) & \le 4d(n / 2)^2 - 4c(n / 2) + cn \\\\ & = dn^2 - cn. \end{aligned} \]

• For \(\Omega(n^2)\), we guess \(T(n) \ge dn^2 - cn\),

  \[ \begin{aligned} T(n) & \ge 4d(n / 2)^2 - 4c(n / 2) + cn \\\\ & = dn^2 - cn. \end{aligned} \]

4.4-8

Use a recursion tree to give an asymptotically tight solution to the recurrence \(T(n) = T(n - a) + T(a) + cn\), where \(a \ge 1\) and \(c > 0\) are constants.

• The tree has \(n / a + 1\) levels.

  The total cost over all nodes at depth \(i\), for \(i = 0, 1, 2, \ldots, n / a - 1\), is \(c(n - ia)\).

  \[ \begin{aligned} T(n) & = \sum_{i = 0}^{n / a} c(n - ia) + (n / a)ca \\\\ & = \sum_{i = 0}^{n / a} cn - \sum_{i = 0}^{n / a} cia + (n / a)ca \\\\ & = cn^2/a - \Theta(n) + \Theta(n) \\\\ & = \Theta(n^2). \end{aligned} \]

• For \(O(n^2)\), we guess \(T(n) \le cn^2\),

  \[ \begin{aligned} T(n) & \le c(n - a)^2 + ca + cn \\\\ & \le cn^2 - 2can + ca + cn \\\\ & \le cn^2 - c(2an - a - n) & (a > 1 / 2, n > 2a) \\\\ & \le cn^2 - cn \\\\ & \le cn^2 \\\\ & = \Theta(n^2). \end{aligned} \]

• For \(\Omega(n^2)\), we guess \(T(n) \ge cn^2\),

  \[ \begin{aligned} T(n) & \ge c(n - a)^2 + ca + cn \\\\ & \ge cn^2 - 2acn + ca + cn \\\\ & \ge cn^2 - c(2an - a - n) & (a < 1 / 2, n > 2a) \\\\ & \ge cn^2 + cn \\\\ & \ge cn^2 \\\\ & = \Theta(n^2). \end{aligned} \]

4.4-9

Use a recursion tree to give an asymptotically tight solution to the recurrence \(T(n) = T(\alpha n) + T((1 - \alpha)n) + cn\), where \(\alpha\) is a constant in the range \(0 < \alpha < 1\), and \(c > 0\) is also a constant.

We can assume that \(0 < \alpha \le 1 / 2\), since otherwise we can let \(\beta = 1 − \alpha\) and solve it for \(\beta\).

Thus, the depth of the tree is \(\log_{1 / \alpha} n\) and each level costs \(cn\). And let's guess that the leaves are \(\Theta(n)\),

We can also show \(T(n) = \Theta(n\lg n)\) by substitution.

To prove the upper bound, we guess that \(T(n) \le dn\lg n\) for a constant \(d > 0\),

where the last step holds when \(d \ge \frac{-c}{\alpha\lg\alpha + (1 - \alpha)\lg(1 - \alpha)}\).

We can achieve this result by solving the inequality

To prove the lower bound, we guess that \(T(n) \ge dn\lg n\) for a constant \(d > 0\),

where the last step holds when \(0 < d \le \frac{-c}{\alpha\lg\alpha + (1 - \alpha)\lg(1 - \alpha)}\).

We can achieve this result by solving the inequality

Therefore, \(T(n) = \Theta(n\lg n)\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用