3
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Avra
    Sep 25 at 20:47
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Appreciated. Very clear solution. $\endgroup$
    – Avra
    Sep 25 at 20:47
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thank you very much. Can you please add a little to what is dash sign in $T^{-}(n)$ and something for $+$ sign in $T^{+}$? $\endgroup$
    – Avra
    Sep 25 at 20:49
  • 1
    $\begingroup$ 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. $\endgroup$
    – Steven
    Sep 25 at 20:53
  • $\begingroup$ Very clear and easy to follow. Thanks. $\endgroup$
    – Avra
    Sep 25 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.