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

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 mean if theres any constant a left up top than its ok to use the solution for case 1?
 Master theorem. I dont understand the epsilon part for case #1.

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

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!