Master Theorem the Master Theorem applies to recurrences of the following form:

Question

Master Theorem the Master Theorem applies to recurrences of the following form: T(n) aT(n/b) f(n) where a 21 and b 1 are constants and f(m) is an asymptotically positive function. There are 3 cases: 1. If f(n) O(nogs a-e) for some constant E> 0, then T(n) e(nlogo a). 2. If f(n) e(nogs a og n) with k 20, then T(n) 0(nogt k+1 n). 3. If f(n) log, a+e with e 0, and f(m) sassies the regularity condition, then T(n) e(f(n)). Regularity condition: af(n/b) Sc (m) for some constant c 1 and all sufficiently large n. The Master Theorem applies to recurrences of the following form: T(n) (n/b) f(n) Give an expression for the runtime T(n) if the recurrence can be solved with the Master Theorem. f the Master Theorem doesn't apply, simply type in none for both sections Answer: 0 Using Case

Explanation / Answer

Since T(n) = 64n T(n/2) + nn is not in the form of T(n) = aT(n/b) + f(n) because mulitplier of T(n/b) is a constant and not a function of n. Therefore, master theorem cannot be applied to this equation.

So, answer is simply "none" for both of the blanks

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

---