Verify if T(n) = T(n/2) + log(n) - Recurrence Relation

588 Views Asked by At

I'm not sure if I'm correct, but could you please verify if this is right:

$$\begin{align} T(n) &= T\left(\frac{n}{2}\right) + log_{2}(n)\\ T(n) &= T\left(\frac{n}{2^{i}}\right) + n\sum_{i-1}^{k=0} \left ( \frac{1}{2} \right )^{i}\\ T(n) &= 1 + n\left[2 - \frac{1}{2^{log(n)-1}}\right] \\ T(n) &= 2n - 1\\ \end{align}$$

I would be very grateful. Thanks.

1

There are 1 best solutions below

2
On

No - for example if $$T(4)=2 \times 4-1=7$$ then $$T(8)=T(4)+\log_2(8)= 7+3=10 \not = 2 \times 8-1.$$

Just looking at powers of 2:

$$T(2)=T(1)+1$$ $$T(4)=T(2)+2=T(1)+3$$ $$T(8)=T(4)+3=T(1)+6$$ $$T(2^n)=T(1)+\frac{n(n+1)}{2}$$