Question

(a) Show that if f(n) = O(f′(n)) and g(n) = O(g′(n)) then f(n) + g(n) =O(f′(n) + g′(n)).    (b)Solve T (n) = T (n − 1) + n2 using the recurrence tree method. In particular, what is big-O of T(n).

Answer 1

a)

Since f(n) = O(f'(n)), this implies

0 <= f(n) <= c1 * f'(n) where c1 is a positive constant --------------> (1)

Since g(n) = O(g'(n)), this implies

0 <= g(n) <= c2 * g'(n) where c2 is a positive constant -------------> (2)

adding 1 and 2, we get

0 <= f(n) + g(n) <= c1 * f'(n) + c2 * g'(n)

0 <= f(n) + g(n) <= c3 * (f'(n) + g'(n)) where c3 is greater than c1 and c2.

Hence, f(n) + g(n) = O(f'(n) + g'(n))

2)

T(n) - T(n-1) = n²

=> T(1) - T(0) = 1

=> T(2) - T(1) = 4

=> T(3) - T(2) = 9

=> T(4) - T(3) = 16

.......

=> T(n) - T(n-1) = n²

Summing every equations, we get

T(n) - T(0) = 1 + 4 + 9 + 16 + .... + n² = n(2n+1)(n+2)/6

=> T(n) = T(0) + O(n³) = O(n³​​​​​​​)