1

I know that the master theorem states that if $n=d^k$: $$ T(n) = CT(n/d) + f(n)\text{ for }k >= 1\text{ and }T(1)= 1 $$

then $$ T(n)=\sum_{j= 0}^k C^j f(n/d^j) $$

Then how do I get $T(n) = k+1$ when solving $T(n) = T(n/2) +1)$ for $n = 2^k$ and $T(1)= 1$? ( Binary Search Recursion). Do I take $C =1, d = 2,f(n) = 1$?

Thanks...

Rick Decker
  • 8,718
Kris
  • 23

1 Answers1

0

I've made some fixes to your problem. See if they're okay. If you have $T(n)$ defined by $$ T(1) = 1\text{ and }T(d^k)=CT(d^{k-1}) + f(d^k)\text{ for }$k\ge 1$ $$ then you (correctly) have $$ T(d^k) = \sum_{j=0}^k C^j f(d^k/d^j)= \sum_{j=0}^k C^j f(d^{k-j}) $$ Then, assuming you meant to apply this to the function defined by $$ T(1)=1\text{ and }T(2^k)=T(2^{k-1})+1\text{ for }k\ge 1 $$ then indeed you would have $C=1, d=2, f(2^k)=1$ in the theorem above and so you'd have $$ T(2^k)=\sum_{j=0}^k 1^j f(2^{k-j})=\sum_{j=0}^k 1\cdot1=k+1 $$

Rick Decker
  • 8,718