5 votes 5 votes The time complexity of recurrence relation T(n) = T(n/3) + T(2n/3) + O(n) is (A) O(Ig n) (B) O(n) (C) O(nIgn) (D) O(n^2 ) Algorithms recurrence-relation + – Sanjay Sharma asked May 11, 2016 Sanjay Sharma 6.5k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
6 votes 6 votes You can see the image Shyam Singh 1 answered May 11, 2016 Shyam Singh 1 comment Share Follow See all 2 Comments See all 2 2 Comments reply srestha commented May 12, 2016 reply Follow Share it will be sigma(nlogn) rt? http://math.stackexchange.com/questions/1112012/recursion-tree-tn-tn-3-t2n-3-cn 1 votes 1 votes Shyam Singh 1 commented May 12, 2016 reply Follow Share Technically yes. Because of the assumption of the depth and perfect binary tree, it has to be Ω(n.logn) 1 votes 1 votes Please log in or register to add a comment.