0 votes 0 votes To prove that the time complexity of equation T(n) = T(α n) + T((1 – α)n) + βn is Θ(n logn). Algorithms time-complexity algorithms recurrence-relation + – pk14697 asked Jul 2, 2018 pk14697 334 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Navneet Kalra commented Jul 2, 2018 reply Follow Share Form a recurrence tree of this equation with root as βn.....\ at each level u will get cost as βn and height of the tree will be (log β+log n)/logα so (βn+βn+βn.......up to above hight will be.... =βn*(logβ+logn)/log α =(βnlogβ)/logα +(βnlogn)/logαΞΘ(nlogn) 0 votes 0 votes nephron commented Oct 31, 2018 reply Follow Share Hint - Use recurrence tree 0 votes 0 votes Please log in or register to add a comment.
