retagged by
5,973 views
2 votes
2 votes

Question:

$T(1)=1$

$T(n) = 2 T(n - 1) + n$

evaluates to?

Can anyone solve it by substitution method?


Given answer 

$T(n) = 2^{n+1} - (n+2)$

How? 

retagged by

3 Answers

0 votes
0 votes

TRICK

put any value in question and answer....if they match then correct solution

 

otherwise solve with substitution method... then you will get the answer

0 votes
0 votes
The answer should be approx O(n 2^n). Yours answer comes only O(2^n).... Which is wrong for sure.
0 votes
0 votes
Solve the by hit and trial method

Put the n= 2

We find  T(2)= 2T(2-1) +2

                        = 2*1+2=4

And the check options is equal to 4

So options (a) is correct

Related questions

0 votes
0 votes
3 answers
1
Priyanka Agarwal asked Jul 11, 2018
1,024 views
0 votes
0 votes
1 answer
2
Manoj Kumar Pandey asked Jun 20, 2018
307 views
We've been given an unordered list having n distinct elements,the no. Of comparison to find an element that is neither the 2nd minimum nor the 2nd maximum is?
0 votes
0 votes
1 answer
3
Shankar Jha asked Jun 15, 2018
575 views
Assume that merge sort algorithm in the worst case takes 30 seconds for an input of size 64 which of The following most closely approximates the maximum input size of a p...