Give asymptotic upper bounds for T(n) satisfying the recurrences in parts (a) and (b). Make your...

 

Transcribed Image Text:

Give asymptotic upper bounds for T(n) satisfying the recurrences in parts (a) and (b). Make your bounds as tight as possible. Note that "tight upper bound" means the best possible Big-O answer. So, T(n) = 0(n°) would not be considered a fully correct answer if T(n) = O(n*) as well. You must prove your results from scratch using either the expansion or tree method shown in class. Show all of your work. For (a) you may assume that n is a power of 3; for (b) you may assume that it is a power of 4. (a) T(1) = 1; T(n) = 10T(n/3) + n? for n > 1. (b) T(1) = 1; T(n) = 16T(n/4) + n? for n > 1. %3D Give asymptotic upper bounds for T(n) satisfying the recurrences in parts (a) and (b). Make your bounds as tight as possible. Note that "tight upper bound" means the best possible Big-O answer. So, T(n) = 0(n°) would not be considered a fully correct answer if T(n) = O(n*) as well. You must prove your results from scratch using either the expansion or tree method shown in class. Show all of your work. For (a) you may assume that n is a power of 3; for (b) you may assume that it is a power of 4. (a) T(1) = 1; T(n) = 10T(n/3) + n? for n > 1. (b) T(1) = 1; T(n) = 16T(n/4) + n? for n > 1. %3D

Answer rating: 100% (QA)

a Let n 4k Tn 6Tn Tn 66T n n 16 Tn 6T 6n n 16 Tn 66T 16... View the full answer