2 votes 2 votes Solve the recurrences. A) T(1) = 1, T(2) = 6, T(3) = 13, and for all n ≥ 4, T(n) = T(n − 3) + 5n − 9. B) T(1) = 1, and for all n ≥ 2, T(n)=2T(n − 1) + n2 − 2n + 1. Algorithms difficult recurrence-relation algorithms + – Prasanna asked Nov 26, 2015 Prasanna 523 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Asymptotic Answers .. a. T(n) = T(n − 3) + 5n − 9 T(n) = T(n − 3) + O(n) Level Cost = O(n), Number of Level = n/3 = O(n) T(n) = Number of Level * Level Cost = O(n) * O(n) = O(n2) b. T(n)=2T(n − 1) + n2 - 2n + 1 T(n)=2T(n − 1) + O(n2) each time two function call, Number of Level = n T(n) = O(2n) Digvijay Pandey answered Nov 26, 2015 Digvijay Pandey comment Share Follow See all 2 Comments See all 2 2 Comments reply Prasanna commented Nov 26, 2015 reply Follow Share level cost and Number of levels here means ? 0 votes 0 votes Himanshu1 commented Nov 28, 2015 reply Follow Share IInd is T(n)=2T(n − 1) + O(n2) which gives T(n) = O(2n * n2) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes T(n) =T(n-3)+5n- 9 T(n)=T(n-3)+O(n) Now use T(n)=aT(n-b)+O(n^k) Condition if a=1 then T(n)=O(n^(k+1)) So and is O(n^2) 2- for second use conditiontion If a>1 then T(n)=O{n^k a^(n/b)} sabir answered Nov 27, 2015 sabir comment Share Follow See all 0 reply Please log in or register to add a comment.