3 votes 3 votes Consider the recurrence equation $T(n) =\begin{cases} 2T(n-1), & \text{if }n>0 \\ 1, & \text{otherwise} \end{cases}$ Then $T(n)$ is (in $big\, O$ order) $O(n)$ $O(2^n)$ $O(1)$ $O(\log n)$ Algorithms isrodec2017 recurrence-relation asymptotic-notation + – gatecse asked Dec 17, 2017 • recategorized Feb 11, 2018 by srestha gatecse 3.0k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply joshi_nitish commented Dec 20, 2017 reply Follow Share T(n) = 2T(n-1), T(0) = 1 solving this linear homogenouss equaition we will get, $T(n)=2^{n}$ so it will be $O(2^{n})$ 4 votes 4 votes Anu007 commented Dec 20, 2017 reply Follow Share isro says O(1) 0 votes 0 votes joshi_nitish commented Dec 20, 2017 reply Follow Share it should be O(2n) only, if it T(0) = 0, then it would be O(1) 1 votes 1 votes Ashwin Kulkarni commented Dec 20, 2017 reply Follow Share Surely O(2n) 1 votes 1 votes Please log in or register to add a comment.
Best answer 9 votes 9 votes $T(n)=2T(n-1)$ $T(n)=2[2T(n-2)]=2^{2}T(n-2)$ $T(n)=2^{2}[2T(n-3)]= 2^{3}T(n-3)$ $T(n)=2^{k}T(n-k)$ $n-k=0, \ n=k,\ T(0)=1$ $T(n)=2^{n}$ Hence option B) is correct Ashwani Kumar 2 answered Dec 20, 2017 • selected Feb 11, 2018 by srestha Ashwani Kumar 2 comment Share Follow See all 4 Comments See all 4 4 Comments reply REGGIE S commented Jan 10, 2018 reply Follow Share They even didnt change this in the revised key... 0 votes 0 votes habedo007 commented Feb 8, 2018 reply Follow Share Maybe because nobody submitted any grievance against it. 0 votes 0 votes papujimmy commented Feb 10, 2018 reply Follow Share I think ISRO is correct. Because the time complexity depends on the workdone. so T(n) = 2T(n - 1) + 0 means with no time it can do that. So directlty we can say that T(n) = 2^n for example T(3) = 8 directly i can say. 0 votes 0 votes Mk Utkarsh commented Feb 13, 2018 reply Follow Share papujimmy no you are a little wrong that extra amount of work you are mentioning is not done in this recurrence, if it is not done or that work is less as compared to recurrence then that is not considered while calculating complexity. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes just do by substitution nd observation for saving tym T(0)=1 given T(1)=2 on putting T(2)=2*2 T(3)=2*2*2 ...............T(n)=2*2*2*2.............n tymes=2^n eyeamgj answered Apr 19, 2018 eyeamgj comment Share Follow See all 0 reply Please log in or register to add a comment.