NIELIT 2018-75

Question

For the given recurrence equation

$\begin{array} T(n) & =2T(n-1), &\text{if } n>0 \\ & =1, & \text{otherwise} \end{array}$

• A. $O(n \log n)$
• B. $O(n^2)$
• C. $O(2^n)$
• D. $O(n)$

Answer 1

$T(0) = 1 = $ $2^{0} $

$T(1) = 2T(0) = 2 = $$ 2^{1} $

$T(2) = 2 T(1) = 2.2 = $ $2^{2} $

$T(3) = 2 T(2) = 2.2.2= $ $2^{3} $

$.......$

$T(n) = 2T(n-1) = 2.2.2.2.2....n times =$ $ 2^{n} $

$\therefore T(n) = O(2^{n})$

Hence Option C is the correct answer.

Answer 2

T(n) = 2T (n - 1) + 1
= 2 [2T(n - 2) + 1] + 1
= 2^2 T(n - 2) + 3
⋮
= 2^kT(n - k) + (2^k - 1)
= 2^n-1T(1) + (2^n-1 - 1)
= 2^n-1+ 2^n-1 - 1
= 2^n - 1
≅ O( 2^n )

Answer 3

by master theorem for decreasing function:

option C is correct.

refer:-> https://www.geeksforgeeks.org/master-theorem-subtract-conquer-recurrences/