2

I have to solve the above recurrence relation using induction method but I am kind of lost. My attempt was

$$T(n)=2T\left(\frac{n}{2}+16\right)+n.$$

Then I took, $\frac{n}{2}+16$ in the place of n

\begin{align*} T(n)&= 2\left[2T\left(\frac{n}{4}+32\right)+ \left(\frac{n}{2}+16\right)\right]+n \\ &=2^2T(n/4+32)+16+n/2+n \\ &=2^2T(n/4+32)+16+n(1+1/2). \end{align*}

Then I took $\frac{n}{4}+32$ in $n's$ place And, $T(n)=2^2\left[2T\left(\frac{n}{8}+48\right)+\left(\frac{n}{4}+32\right)\right]+n$

I don't know if it right or wrong. I am kind of stuck in this point. Should I take $\left(\frac{n}{4}+16\right)$ as $n$ or not ?

Dark Devil
  • 35
  • Does this https://math.stackexchange.com/a/2269351 help you –  Mar 12 '21 at 05:41
  • I just want to know whether I take (n/2+16) as n or not – Dark Devil Mar 12 '21 at 06:52
  • $\frac{n}{2}$ is not always an integer, so this is not well-defined. Do you mean $\left\lfloor\frac{n}{2}\right\rfloor$? (In binary notation, that chops off the units bit.) Also, $\left\lfloor\frac{\left\lfloor\frac{n}{2}\right\rfloor+16}{2}\right\rfloor+16=\left\lfloor\frac{n}{4}\right\rfloor+24$, then we get $\left\lfloor\frac{n}{8}\right\rfloor+28$, $\left\lfloor\frac{n}{16}\right\rfloor+30$, $\left\lfloor\frac{n}{32}\right\rfloor+31$, $\left\lfloor\frac{n}{64}\right\rfloor+31$, etc., so after $\left\lfloor\log_2{n}\right\rfloor+1$ iterations, it's just $31$ repeating. – Alexander Burstein Mar 12 '21 at 09:08

0 Answers0