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

Question

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

Answer 1

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.