2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

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

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.