# Is master theorem applicable to the recurrence relation $T(n) = T(n/2)$?

Is master theorem applicable to the recurrence relation $T(n) = T(n/2)$?

I do not think it applies because there no $n$ term and there is no $n^k$ for a $k$ which would equal $0$.

Forget about master theorem a minute.

The hypothesis clearly states that $T(2^n) = T(0)$. Now if you assume htat $T$ increasing, you get $$T(0)\le T(n) \le T(2^n) = T(0)\implies T(n) = T(0)$$hence $T$ is constant. So why bother with the big theorem?

for practice purpose:

$$T(n)= T(n/2)$$ is the case 1 of the wiki article: $$T(n) = aT(n/b) + f(n)$$ with $0 = f(n) = O(n^c)$ for any $c$, and in particular $c < \log a / \log b$. Hence the master theorem applies and $$T(n) = O(n^{\log a / \log b}) = O(1)$$as $a=1$. So the master theorem gives the right conclusion.

• we are just practicing master theorem and what functions it is applciable – Manny Pwety Oct 20 '14 at 22:34
• @MannyPwety: I edit accordingly my answer. – mookid Oct 20 '14 at 22:45
• here is my source gyazo.com/b9548f57b36372df1e5715d38f578403 – Manny Pwety Oct 20 '14 at 22:52
• OK. here the relation is true with any $k$, so the best case applies. – mookid Oct 20 '14 at 22:58