recategorized by
1,554 views

3 Answers

1 votes
1 votes

$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.

1 votes
1 votes
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:

Related questions

1 votes
1 votes
1 answer
1
Arjun asked Dec 7, 2018
16,948 views
______ sorting algorithms has the lowest worst-case complexity.Selection SortBubble SortMerge SortQuick Sort
0 votes
0 votes
2 answers
2
Arjun asked Dec 7, 2018
1,122 views
Dijkstra’s algorithm is based onGreedy approachDynamic programmingBacktracking paradigmDivide and conquer paradigm
3 votes
3 votes
1 answer
3