Let T(n) be defined by T(1) = 10 and T(n + 1) = 2n + T(n) and for all integers…
2011
Let T(n) be defined by T(1) = 10 and T(n + 1) = 2n + T(n) and for all integers n ≥ 1 . Which of the following represents the order of growth of T(n) as a function of
- A.
O(n)
- B.
O(n log n)
- C.
O(n2)
- D.
O(n3)
Attempted by 108 students.
Show answer & explanation
Correct answer: C
To find the order of growth, we expand the recurrence relation T(n + 1) = 2n + T(n). Unrolling this gives T(n) = T(1) + Σ_{i=1}^{n-1} 2i. Given T(1) = 10, we calculate the sum: Σ_{i=1}^{n-1} i = (n-1)n/2. Therefore, T(n) = 10 + 2 * (n-1)n/2 = 10 + n^2 - n. The dominant term is n^2, indicating the order of growth is O(n^2).