Question: Master theorem. I dont understand the epsilon part for case #1. I know it has to be a number greater than 0 so does that
Theorem 4.1 (Master theorem) Let a1 and b>1 be constants, let f(n) be a function, and let T (n) be defined on the nonnegative integers by the recurrence T(n) = aT(n/b) + f(n). where we interpret n/b to mean either ln/born/b]. Then T(n) has the follow- ing asymptotic bounds: 1. If f(n) = 0(nkngba-e) for some constant > 0, then T(n) = (nlog ). 2. If f(n) = (nlogb a), then T(n) = (nlogba lg n) 3. If f(n) = (nlogba+*) for some constant E > 0, and if af(n/b) cf(n) for b a some constant c
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
