0 votes 0 votes T(n) = T(n/2)+2n find the complexity? A) O(n log n) B)O(n2) C)O(2n) D) O(n) anup9544 asked Oct 16, 2016 anup9544 411 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments amitlko commented Oct 16, 2016 reply Follow Share @mcjoshi, I got the logic. Is it possible to solve this recurrence relation by substitution? 0 votes 0 votes anup9544 commented Oct 16, 2016 reply Follow Share Is it possible by master's theorem 3rd case? 0 votes 0 votes mcjoshi commented Oct 16, 2016 i edited by mcjoshi Oct 16, 2016 reply Follow Share Yes, it is possible to do it using substitution and for master's theorem see example-3 here 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes by applying master theorem if n^logb(a) is >f(n) then tc=o(n^logb(a)) else n^logb(a)==f(n) then tc=o(n^logb(a)logn) else o(f(n)) coming to given problem n^log2(1)<2^n then TC=O(2^n) santhoshdevulapally answered Nov 1, 2016 santhoshdevulapally comment Share Follow See all 0 reply Please log in or register to add a comment.