Exercise 4.5-5

[clear-life]

The answer is correct，but the process of the proof is wrong. It asks us to prove a * f(n/b)≤c * f(n) for c<1 is invalid. Now a=1, b=2 ,f(n)=n(2−cosn). So the first step is (n/2) * (2−cos(n/2)) < c * n(2−cosn)

[clear-life]

Now I found another bug:f(n)= n(2−cosn) maybe is not equal to Ω(n^(1+ε)) for some constant ε > 0. So f(n)=n(2−cosn) doesn‘t meet the condition of the master theorem case 3.

[run27017]

@clear-life Due to a=1, b=2, the polynomial is n^{lg 1}, which is 1, so f(n) only need to be in Ω(n^ε).