Consider the recurrence equation T(n) = 2T(n-1), if n>0 = 1, otherwise Then…
2017
Consider the recurrence equation
T(n) = 2T(n-1), if n>0
= 1, otherwise
Then T(n) is (in big O order)
- A.
O(n)
- B.
O(2n)
- C.
O(1)
- D.
O(log n)
Attempted by 105 students.
Show answer & explanation
Correct answer: B
To solve the recurrence T(n) = 2T(n-1), we expand it iteratively starting from n down to the base case.
T(n) = 2 * T(n-1) = 2 * (2 * T(n-2)) = ... = 2^n * T(0)
Given T(0) = 1, we have T(n) = 2^n. Therefore, the time complexity is O(2^n).