6. [15 points] The Master theorem states the following: 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 n/b interpret to mean either n/b or n/b Then the T(n) can be bounded asymptotically as follows. 1. If f(n)=O(nlogba) for some constant >0, then T(n)=(nlogba). 2. If f(n)=O(nlogba), then T(n)=(nlogbalgn) 3. If f(n)=O(nlogba+) for some constant >0, and if af(n/b)cf(n) for some constant