In the following recurrence what are a and b?
T(n)=3T(n/2)+n

Question

BlackTom AI · Accepted Answer

Master Theorem form is T(n) = a T(n/b) + f(n), so the recurrence T(n) = 3 T(n/2) + n maps directly to a and b.

1) Relevant knowledge points and concepts
- Standard divide-and-conquer recurrence form: T(n) = a T(n/b) + f(n), where a = number of subproblems and b = factor by which the input size is divided.
- For complexity classification, compare f(n) to n^{log_b a} (here log_b a = log_2 3 ≈ 1.585).

2) Complete reasoning process step by step
- Identify the subproblem term: T(n/2). The argument n/2 indicates the input size is divided by 2, so b = 2.
- Identify the multiplicative coefficient on T(...): it is 3 in front of T(n/2), so a = 3.

3) Intermediate calculation steps
- Write recurrence in canonical form: T(n) = a T(n/b) + f(n) = 3 T(n/2) + n.
- Thus a = 3, b = 2.
- (Optional classification) Compute n^{log_b a} = n^{log_2 3} ≈ n^{1.585}. Compare f(n)=n = n^{1} which is polynomially smaller, so by Master Theorem case 1, T(n) = Theta(n^{log_2 3}).

4) Why the correct answer is correct
- The coefficient 3 directly counts the subproblems, so a = 3. The division inside T(...) is n/2, meaning the size is reduced by a factor of 2 each recursion, so b = 2. This is the exact mapping required by the Master Theorem form.

5) Why the other options are incorrect
- "3 and n/2": b should be the numeric divisor (2), not the expression n/2. Listing "n/2" as b is a misinterpretation.
- "3 and n": b cannot be n; b is a constant factor, not the variable n.
- "2 and 3": this swaps the roles; here a is not 2 and b is not 3 because the recurrence has 3 subproblems of size n/2, not 2 subproblems of size n/3.

6) Conclusion
- Therefore a = 3 and b = 2, matching the provided correct answer "3 and 2."

In the following recurrence what are a and b? T(n)=3T(n/2)+n单项选择题

类似问题

In case 2 of the master theorem, If f(n) = O(n^k) where k = logb(a), then---------------.

In the context of the Master Theorem 𝑇 ( 𝑛 ) = 𝑎 𝑇 ( 𝑛 / 𝑏 ) + 𝑓 ( 𝑛 ) , the total work done by all internal nodes in the recursion tree is primarily determined by:

What is the asymptotic behavior of T(n) = 2T(n/2) + O(1)? Select the tightest bound that holds.

What is the asymptotic behavior of T(n) = 4T(n/2) + O(n2)? Select tightest bound that holds.

What is the asymptotic behavior of T(n) = 4T(n/2) + O(n3)? Select tightest bound that holds.

What is the asymptotic behavior of T(n) = 4T(n/2) + O(n)? Select tightest bound that holds.

What is the asymptotic behavior of T(n) = 4T(n/2) + O(1)? Select tightest bound that holds.

What is the asymptotic behaviour of T(n) = T(n/2) + O(n)? Select the tightest bound that holds.

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单