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? Algorithms time-complexity algorithms recurrence-relation made-easy-booklet + – Jyoti Kumari97 asked May 25, 2019 retagged Jul 8, 2022 by Lakshman Bhaiya Jyoti Kumari97 6.0k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply abhishekmehta4u commented May 25, 2019 reply Follow Share O(2^n) –1 votes –1 votes Astitva Srivastava commented May 26, 2019 reply Follow Share What I think is that if you try to somehow convert the expression you are getting into the given answer it's not easy and not obvious. The question seems like selection and elimination type. If you have four options then successively find out values, say upto T(5), and see which option's result is matching with your result. There will be a way to adjust the expression by adding or subtracting some terms to get the answer but it will be cubersome. 0 votes 0 votes Kabir5454 commented Jul 8, 2022 reply Follow Share https://gateoverflow.in/19033/t-c-of-t-n-2t-n-1-n-n-1-t-1-1 Derivation of these problem 0 votes 0 votes Please log in or register to add a comment.
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 vikash_thakur answered Jun 15, 2019 vikash_thakur comment Share Follow See all 0 reply Please log in or register to add a comment.
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. v.singhal7040 answered Jul 31, 2019 v.singhal7040 comment Share Follow See all 0 reply Please log in or register to add a comment.
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 DKY123 answered Jan 12, 2020 DKY123 comment Share Follow See all 0 reply Please log in or register to add a comment.