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 Show 3 previous comments 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.