3 votes 3 votes T(n) = T$(\frac{n}{3})$ + T$(\frac{2n}{3})$ + O(n) Algorithms algorithms time-complexity asymptotic-notation recurrence-relation + – LavTheRawkstar asked May 7, 2017 retagged Jun 4, 2017 by Arjun LavTheRawkstar 1.6k views answer comment Share Follow See 1 comment See all 1 1 comment reply LavTheRawkstar commented May 7, 2017 reply Follow Share somebody please tell this 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes This is of the form:-T(n)=T(an)+T((1-a)n)+bn where a=1/3 so 1-a=2/3. The solution of this type of relation is: t(n)=O(nlogn). Purvi Agrawal answered May 7, 2017 Purvi Agrawal comment Share Follow See all 6 Comments See all 6 6 Comments reply LavTheRawkstar commented May 7, 2017 reply Follow Share dear mam please draw the recursion tree and show how it is coming n log n i am totallt confused 0 votes 0 votes shraddha_gami commented May 7, 2017 reply Follow Share i only shown one sided b'cz it is growing more in that side 2 votes 2 votes LavTheRawkstar commented May 7, 2017 reply Follow Share https://gateoverflow.in/128482/solve-recurrence-using-master-total-confusion-fraction-there?show=128611#c128611 mam please tell this please –1 votes –1 votes Nit9 commented Oct 28, 2017 reply Follow Share @lav Height is k and acc. To eq. Work done outside recurrsive calls is O(n) So total work done = O(nk) = O(nlogn) 0 votes 0 votes sourav. commented Oct 28, 2017 reply Follow Share should be$O(n \log_{3}n)$ 0 votes 0 votes Nit9 commented Oct 28, 2017 reply Follow Share Log Base 3/2 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Can be done using recursion tree method 5a1n1amarjeet answered Jun 26, 2021 5a1n1amarjeet comment Share Follow See all 0 reply Please log in or register to add a comment.