ISRO | CS ISRO 2011 | Pregunta 56

Sea T(n) definida por T(1) = 10 y T(n + 1) = 2n + T(n) y para todos los enteros n ≥ 1 . ¿Cuál de los siguientes representa el orden de crecimiento de T(n) en función de
(A) O(n)
(B) O(n log n)
(C) O(n ² )
(D) O(n ³ )

Respuesta: (C)
Explicación:

T(n + 1) = 2n + T(n) 
By substitution method:
T(n + 1) = 2n + (2(n-1) + T(n-1))
T(n + 1) = 2n + (2(n-1) + (2(n-2) + T(n-2)))
T(n + 1) = 2n + (2(n-1) + (2(n-2) + (2(n-3) + T(n-3))))
T(n + 1) = 2n + 2(n-1) + 2(n-2) + 2(n-3)......2(n-(n-1) + T(1))
T(n + 1) = 2n + 2n - 2 + 2n - 4 + 2n - 6 +.... + 10
T(n + 1) = 2[n + n + n + ...] - 2[1 + 2 + 3 +...]
T(n + 1) = 2[n*n] - 2[n(n+1)/2]
T(n + 1) = 2[n*n] - [n*n + n]
T(n + 1) = n*n - n
T(n + 1) = O(n2)

Cuestionario de esta pregunta