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

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.)

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.

• Sometimes your solutions are very advanced, but this one is very easy to follow. Thank you. So you just find that range of $2−cosn$ is of $O(n)$ order, so I was doing something close in my attemp.
– Avv
Sep 25 '21 at 20:47

$$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)$$.

• Appreciated. Very clear solution.
– Avv
Sep 25 '21 at 20:47

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)$$.

• Thank you very much. Can you please add a little to what is dash sign in $T^{-}(n)$ and something for $+$ sign in $T^{+}$?
– Avv
Sep 25 '21 at 20:49
• I just needed different names for the recurrences I defined. I used $T^-$ and $T^+$ since they are a lower bound and an upper bound to $T$, respectively. Sep 25 '21 at 20:53
• Very clear and easy to follow. Thanks.
– Avv
Sep 25 '21 at 20:59