Use the master method to give tight asymptotic bounds for the following recurrences.
a.
b.
c.
a.
b.
c.
The recurrence T(n) = 7T (n/2)+n2 describes the running time of an algorithm A. A competing algorithm A′ has a running time of T′(n) = aT′(n/4) + n2. What is the largest integer value for a such that A′ is asymptotically faster than A?
根据主定理，算法A的运行时间为%20=%20\\Theta\(\\lg{7}\)\ \approx%20n^{2.8}%20)
A'的运行时间在a > 16时超过n^2,此时
所以最大值为48
Use the master method to show that the solution to the binary-search recurrence T(n) = T (n/2)
- Θ(1) is T(n) = Θ(lg n). (See Exercise 2.3-5 for a description of binary search.)
so the solution is Θ(lgn).
Can the master method be applied to the recurrence
Why or why not? Give an asymptotic upper bound for this recurrence.
The problem is that it is not polynomially larger. The ratio 
is asymptotically less than
for any positive constant
Consider the regularity condition af (n/b) ≤ cf(n) for some constant c < 1, which is part of case 3 of the master theorem. Give an example of constants a ≥ 1 and b > 1 and a function f (n) that satisfies all the conditions in case 3 of the master theorem except the regularity condition.
let
a = 1
b = 2
f(n) = 2n - n * cos(n)We are in Case 3, but the regularity condition is violated. (Consider n = 2πk, where k is odd and arbitrarily large. For any such choice of n, you can show that c ≥ 3/2, thereby violating the regularity condition.)
Follow @louis1992 on github to help finish this task.