master theorem

Question

explain complexity for this 

Comments

it will be O(n) ,

n(2-cosn)= O(n)

---

see point number 22

---

http://www.csd.uwo.ca/~moreno//CS424/Ressources/master.pdf

---

@Bikram sir

Answer 1

See the value of $\cos(n)$ will oscillate between $-1$ or $1$ thus makes $f(n)$ between $n$ & $3n$. In both of the cases, complexity turns out to be $\theta(n)$ only.

Comments

T (n) = T (n/2) + n(2 − cos n) =⇒ 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 ≥ 3/2, thereby violating the regularity condition.)

---

Can someone explain me this example? I read that pdf too...but couldn't understand this example....pls pls pls

---

@debasree88 Have a look at my solution. Hope it helps. Pardon for bad handwriting.