1 votes 1 votes Complexity of equation - T(n)=. 2T(n-1)-1 if n>0 1. Otherwise Algorithms recurrence-relation time-complexity + – Surya Dhanraj asked Oct 15, 2017 • retagged Jun 23, 2022 by Lakshman Bhaiya Surya Dhanraj 527 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Rishabh Gupta 2 commented Oct 15, 2017 reply Follow Share O(1) . 0 votes 0 votes Surya Dhanraj commented Oct 15, 2017 reply Follow Share Right ....Can give detail explanation... 0 votes 0 votes Rishabh Gupta 2 commented Oct 15, 2017 reply Follow Share T(0) = 1 T(1) = 2T(0) - 1 = 1 T(2) = 2T(1) - 1 = 1 T(3) = 2T(2) - 1 = 1 ... T(i) = 1 Therefore, T does not depend on the input n. It is always 1 (constant). Hence complexity is O(1) 2 votes 2 votes Surya Dhanraj commented Oct 15, 2017 reply Follow Share Thanku @rishabh gupta 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Edited! Sorry that was some dumb mistake @suraj Abhijit Howal answered Oct 15, 2017 • edited Oct 15, 2017 by Abhijit Howal Abhijit Howal comment Share Follow See 1 comment See all 1 1 comment reply Surya Dhanraj commented Oct 15, 2017 reply Follow Share @abhijit procedure is right but at last u have written wrong Answer is O(1) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes T(n)=2T(n-1) - 1, n>0 T(0)=1 T(n)=2T(n-1)-1 T(n)=2(2(T(n-2)-1)-1 = 22T(n-2)-3 // T(n-1)=2T(n-2)-1 T(n)=2(2(2T(n-3)-1))-3 = 23T(n-3)-7 // T(n-2)=2T(n-3)-1 T(n)=2kT(n-k)-(2k-1) When n=k T(n)=2nT(0)-(2n-1)= 2n-2n+1=1=O(1) Pawan Kumar 2 answered Oct 15, 2017 Pawan Kumar 2 comment Share Follow See all 0 reply Please log in or register to add a comment.