3 votes 3 votes T(n) = T(n/2) + 2T(n/5) + T(n/10) + 4n What is the time complexity for the recursion above? Algorithms time-complexity algorithms recurrence-relation + – Warlock lord asked Dec 5, 2017 retagged Jul 8, 2022 by Lakshman Bhaiya Warlock lord 947 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Anu007 commented Dec 5, 2017 reply Follow Share O(nlogn)...... 0 votes 0 votes Bunty Chakraborty commented Jan 3, 2018 reply Follow Share how?? 0 votes 0 votes Priyadrasta Raut commented Oct 21, 2019 reply Follow Share I think the longest path is of T(n/2) that means in worst case we can say time complexity is O(nlogn) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes It will be O(n). Let T1(n)=T(n/2) + n. Then using Master's theorem, T1(n) = O(n) Let T2(n) = 2T(n/5) + 2n. Again using Master's theorem T2(n) = O(n). Let T3(n)= T(n/10) +n . So T3(n) = O(n). T(n) = T1(n) + T2(n) + T3(n) = O(n) + O(n) + O(n) = O(n). sumedha bhatia answered Jan 31, 2018 sumedha bhatia comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments sumedha bhatia commented Jan 31, 2018 reply Follow Share Thanks. That helped. 1 votes 1 votes sumit goyal 1 commented Jan 31, 2018 reply Follow Share welcome 0 votes 0 votes aarju commented Feb 2, 2018 reply Follow Share i am sure ans is o(n) 0 votes 0 votes Please log in or register to add a comment.