For each of the following recurrence relations, pick the correct asymptotic runtime: (a) [5 points] Select the correct asymptotic complexity of an algorithm with runtim \( T(n, n) \) where \[ \begin{aligned} T(x, c) & =\Theta(x) & & \text { for } c \leq 2 \\ T(c, y) & =\Theta(y) & & \text { for } c \leq 2, \text { and } \\ T(x, y) & =\Theta(x+y)+T(x / 2, y / 2) & & \end{aligned} \] 1. \( \Theta(\log n) \). 2. \( \Theta(n) \). 3. \( \Theta(n \log n) \). 4. \( \Theta\left(n \log ^{2} n\right) \). 5. \( \Theta\left(n^{2}\right) \). 6. \( \Theta\left(2^{n}\right) \). (b) [5 points] Select the correct asymptotic complexity of an algorithm with runtim \( T(n, n) \) where \[ \begin{array}{ll} T(x, c)=\Theta(x) & \text { for } c \leq 2 \\ T(c, y)=\Theta(y) & \text { for } c \leq 2, \text { and } \\ T(x, y)=\Theta(x)+T(x, y / 2) & \end{array} \] 1. \( \Theta(\log n) \). 2. \( \Theta(n) \). 3. \( \Theta(n \log n) \). 4. \( \Theta\left(n \log ^{2} n\right) \). 5. \( \Theta\left(n^{2}\right) \). 6. \( \Theta\left(2^{n}\right) \). (c) [5 points] Select the correct asymptotic complexity of an algorithm with runtin \( T(n, n) \) where \[ \begin{array}{rlrl} T(x, c) & =\Theta(x) & \text { for } c \leq 2 \\ T(x, y) & =\Theta(x)+S(x, y / 2), & & \\ S(c, y) & =\Theta(y) & \text { for } c \leq 2, \text { and } \\ S(x, y) & =\Theta(y)+T(x / 2, y) & \end{array} \] 1. \( \Theta(\log n) \). 2. \( \Theta(n) \). 3. \( \Theta(n \log n) \). 4. \( \Theta\left(n \log ^{2} n\right) \). 5. \( \Theta\left(n^{2}\right) \).

To solve the recurrence relations and determine their asymptotic complexities, we will analyze each part step by step. ### (a) The recurrence relation is: \[ \begin{aligned} T(x, c) & =\Theta(x) & \text { for } c \leq 2 \\ T(c, y) & =\Theta(y) & \text { for } c \leq 2, \text { and } \\ T(x, y) & =\Theta(x+y)+T(x / 2, y / 2) & & \end{aligned} \] 1. **Base Cases**: - For \( c \leq 2 \), \( T(x, c) = \Theta(x) \) and \( T(c, y) = \Theta(y) \). 2. **Recursive Case**: - The recursive case \( T(x, y) = \Theta(x+y) + T(x/2, y/2) \) suggests that we are combining the results of two smaller problems. 3. **Analysis**: - The term \( \Theta(x+y) \) dominates the recursion. - Each time we call \( T(x/2, y/2) \), we are halving both \( x \) and \( y \). - This leads to a logarithmic depth of recursion, where at each level we are adding \( \Theta(x+y) \). 4. **Final Complexity**: - The total work done at each level of recursion is \( \Theta(n) \) (where \( n \) is the maximum of \( x \) and \( y \)), and there are \( \log n \) levels. - Thus, the overall complexity is \( \Theta(n \log n) \). **Answer for (a)**: \( \Theta(n \log n) \). --- ### (b) The recurrence relation is: \[ \begin{array}{ll} T(x, c)=\Theta(x) & \text { for } c \leq 2 \\ T(c, y)=\Theta(y) & \text { for } c \leq 2, \text { and } \\ T(x, y)=\Theta(x)+T(x, y / 2) & \end{array} \] 1. **Base Cases**: - Similar to part (a), we have \( T(x, c) = \Theta(x) \) and \( T(c, y) = \Theta(y) \) for \( c \leq 2 \). 2. **Recursive Case**: - The recursive case \( T(x, y) = \Theta(x) + T(x, y/2) \) indicates that we are reducing \( y \) by half at each step while keeping \( x \) constant. 3. **Analysis**: - The term \( \Theta(x) \) is constant for each recursive call, and we will make \( \log y \) calls until \( y \) becomes small enough. - Therefore, the total work done is \( \Theta(x) \) multiplied by the number of levels, which is \( \log y \). 4. **Final Complexity**: - Since \( x \) is constant in terms of \( y \), the overall complexity is \( \Theta(x \log n) \), where \( n \) is the size of \( y \). **Answer for (b)**: \( \Theta(n) \). --- ### (c) The recurrence relation is: \[ \begin{array}{rlrl} T(x, c) & =\Theta(x) & \text { for } c \leq 2 \\ T(x, y) & =\Theta(x)+S(x, y / 2), & & \\ S(c, y) & =\Theta(y) & \text { for } c \leq 2, \text { and } \\ S(x, y) & =\Theta(y)+T(x / 2, y) & \end{array} \] 1. **Base Cases**: - Again, we have \( T(x, c) = \Theta(x) \) and \( S(c, y) = \Theta(y) \) for \( c \leq 2 \). 2. **Recursive Cases**: - The recursive case for \( T(x, y) \) is \( T(x, y) = \Theta(x) + S(x, y/2) \). - The recursive case for \( S(x, y) \) is \( S(x, y) = \Theta(y) + T(x/2, y) \). 3. **Analysis**: - The recursion for \( T(x, y) \) will call \( S(x, y/2) \), which will then call \( T(x/2, y) \). - This creates a nested recursion where both \( x \) and \( y \) are halved at different stages. 4. **Final Complexity**: - The depth of recursion will be \( \log n \) for both \( x \) and \( y \), leading to a total complexity of \( \Theta(n \log n) \). **Answer for (c)**: \( \Theta(n \log n) \). --- ### Summary of Answers: - (a) \( \Theta(n \log n) \) - (b) \( \Theta(n) \) - (c) \( \Theta(n \log n) \)