1 votes 1 votes Base condition T(n) = 1 Otherwise T(n) = T(n-1) +n Then After solving i got to this step ...how should i generalize now T(n) = T( n-k) + n-(k-1) + n-(k-2)+n Algorithms algorithms recurrence-relation + – aka 53 asked Nov 25, 2017 aka 53 304 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 0 votes 0 votes T(n)=T(n-1)+n; T(n-1)=T(n-2)+n-1; T(n-2)=T(n-3)+n-2; T(n)=T(n-2) +n +n-1; T(n)=T(n-3)+n-2+n-1+n; T(n)=T(n-k) +n*k -(1+2+3....k); now at k=n we get T(0)=1; so T(n)=T(0)+n*n- (1+2+3....n); we get n^2-n(n+1)/2 T(n)=O(n^2) Red_devil answered Nov 25, 2017 selected Nov 25, 2017 by aka 53 Red_devil comment Share Follow See all 3 Comments See all 3 3 Comments reply aka 53 commented Nov 25, 2017 reply Follow Share T(n)=T(n-k) +n*k -(1+2+3....k); Pls how you took n*k 0 votes 0 votes kirti_k commented Nov 25, 2017 reply Follow Share When we substitute values for T(n), at one step we got T(n)=T(n-3)+n+n+n-2-1 =T(n-3)+n*3-(1+2) =T(n-k) + n*k -(1+2+3+...k) 1 votes 1 votes aka 53 commented Nov 25, 2017 reply Follow Share Thanks that really helped 0 votes 0 votes Please log in or register to add a comment.