PA of Algorithms Q41
0. The recurrence equation: T(1) = 1 T(n) = 2T(n–l) + n, n ≥ 2 evaluates to
- Option : A
- Explanation : T (1) = 1 T (n) = 2 T (n–1) + n , n ≥ 2 if n = 2 then T (2) = 2 T (1) + 2 = 2 × 1 + 2 = 4 if n = 3 then T (3) = 2 T (2) + 3 = 2* 4 + 3 = 11 Put n = 3 in option (A) 24 – 3 – 2 = 16 – 3 – 2 = 11 so option (A) is true.
