Let T(n) be defined by T(1) = 7 and T(n+1) = 3n + T(n) for all integers n ≥ 1.…
2022
Let T(n) be defined by T(1) = 7 and T(n+1) = 3n + T(n) for all integers n ≥ 1. Which of the following represents the order of growth of T(n)?
- A.
Θ(n)
- B.
Θ(n log n)
- C.
Θ(n²)
- D.
Θ(2ⁿ)
Attempted by 149 students.
Show answer & explanation
Correct answer: C
Key idea: Unroll the recurrence and sum the arithmetic series.
Unwrap the first values: T(1) = 7, T(2) = 7 + 3·1, T(3) = 7 + 3(1+2), and so on.
General form: T(n) = 7 + 3(1 + 2 + ... + (n - 1)).
Sum formula: 1 + 2 + ... + (n - 1) = (n - 1)n/2.
Compute T(n): T(n) = 7 + 3·(n - 1)n/2 = (3/2)n^2 - (3/2)n + 7.
Conclusion: The dominant term is (3/2)n^2, so T(n) = Θ(n^2).