2 votes 2 votes QUESTION 41 : Consider the recurrence relation T(n) = T(n–1) + T(n/2) + n. Which of the following is a good tight upper bound on T(n) (A) Θ(n2) (B) Θ(n2 log n) (C) Θ(2 (log n)2) (D) Θ(n (log n)2) Pooja Palod asked Jan 26, 2016 Pooja Palod 247 views answer comment Share Follow See 1 comment See all 1 1 comment reply Arjun commented Jan 26, 2016 reply Follow Share I would say this is out of GATE level. http://math.stackexchange.com/questions/518682/solve-tn-tn-1t-fracn2n 1 votes 1 votes Please log in or register to add a comment.