What would be the efficiency class of the algorithm based on the master theorem? RE. The...

Transcribed Image Text:

What would be the efficiency class of the algorithm based on the master theorem? RE. The master theorem is as follows T(n) = aT(n/b) + f (n) where f(n) e O(nk), k20 If a < b*, T(n) e ©(n*) If a = bk, T(n) e O(nk log n) If a > bk, T(n) e ©(n'o9 b") Decrease-by-a-constant-factor recurrences - The Master Theorem T(n) = aT(n/b) + f (n), k>=0 where f (n) e O(nk), 1. a < bk 2. a = bk 3. а > bk T(n) e O(nk) T(n) E O(nk log n) T(n) e O(nlog ba) Examples: T(n) = T(n/2) + 1 T(n) = 2T(n/2) + n² - T(n) = 3 T(n/2) + n O(logn) O(n?) %3D O(nlo9,3) %3D 25 What would be the efficiency class of the algorithm based on the master theorem? RE. The master theorem is as follows T(n) = aT(n/b) + f (n) where f(n) e O(nk), k20 If a < b*, T(n) e ©(n*) If a = bk, T(n) e O(nk log n) If a > bk, T(n) e ©(n'o9 b") Decrease-by-a-constant-factor recurrences - The Master Theorem T(n) = aT(n/b) + f (n), k>=0 where f (n) e O(nk), 1. a < bk 2. a = bk 3. а > bk T(n) e O(nk) T(n) E O(nk log n) T(n) e O(nlog ba) Examples: T(n) = T(n/2) + 1 T(n) = 2T(n/2) + n² - T(n) = 3 T(n/2) + n O(logn) O(n?) %3D O(nlo9,3) %3D 25

Answer rating: 100% (QA)

Tcnl 7Cnl TC... View the full answer