Solve $T (n) = T (\frac n2) + n(2 - \cos n)$

Question

For the following recurrence relation:

$$T (n) = T (n/2) + n(2 - \cos n)$$

I see it based on values of $\cos$ function given that it output values in range, but this does not seem to have anything to do with solving the problem. I found a solution which says that comparing this to master method yields that this does not apply to master method, so please based on master method why the previous recurrence relation does not apply based on 3 cases we have?

Solution Found: Does not apply. 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 \ge 3/2$, thereby violating the regularity condition.)

Answer 1

Since $|\cos n| \leq 1$, we have $1 \leq 2-\cos n \leq 3$, and so $$ T(n) = T(n/2) + \Theta(n). $$ This is something that the master theorem can handle.

Answer 2

$n(2-\cos n)$ always lies between $n$ and $3n$.

On expansion, we get:

$T(n) \leq 3 (n+n/2+n/4+\dotsc+1) \leq 6n$

and

$T(n) \geq (n+n/2+n/4+\dotsc+1) \geq n$

Hence, $T(n) = \Theta(n)$.

Answer 3

Define $T^-(n) = T^-(n/2) + n$ and $T^+(n) = T^+(n/2) + 3n$. You can see that $T^-(n) \le T(n) \le T^+(n)$.

Since the master theorem applies to both $T^-(n)$ and $T^+(n)$ which have solution $\Theta(n)$, you can also conclude that $T(n)=\Theta(n)$.