patternMinor
Solve $T (n) = T (\frac n2) + n(2 - \cos n)$
Viewed 0 times
fraccossolve
Problem
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.)
$$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.)
Solution
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.
Context
StackExchange Computer Science Q#144224, answer score: 5
Revisions (0)
No revisions yet.