Explore BrainMass
Share

Recurrence Running Time

Give asymptotic upper and lower running time bounds for T(n) for each of the recurrences. Assume that T(n) is constant for n <= 2. Make bounds as tight as possible, and justify solutions.

a) T(n) = 2*T(n/2) + n^3

b) T(n) = T(9n/10) + n

c) T(n) = 16*T(n/4)+n^2

d) T(n) = 7*T(n/3) + n^2

e) T(n) = 7*T(n/2) + n^2

© BrainMass Inc. brainmass.com August 20, 2018, 4:10 pm ad1c9bdddf

Solution Summary

Recurrence running times are analyzed. The asymptotic upper and lower running time bounds for functions are determined.

$2.19