In: Computer Science
Using Θ-notation, provide asymptotically tight bounds in terms
of n for the solution to each of
the following recurrences. Assume each recurrence has a non-trivial
base case of T(1) = Θ(1).
For example, if asked to solve T(n) = 2T(n/2) + n, then your answer
should be Θ(n log n).
Give a brief explanation for each solution.
(a) T(n) = 5T(n/2) + n
(b) T(n) = 4T(n/2) + n2
(c) T(n) = T(n/4) + T(n/2) + n