Question

Solve the recurrence by substitution method.
T(n) = 2T (n/2)+n-1 and T (1) =1.

Answer 1

Let's substitute the following expressions into our equation :

$$T(n)=2T\left(n/2\right)+n-1\longrightarrow\\[0.3cm] \left\{\begin{array}{l} n\to n/2 :\quad T\left(n/2\right)=2T\left(n/4\right)+n/2-1\\[0.3cm] n\to n/4 :\quad T\left(n/4\right)=2T\left(n/8\right)+n/4-1\\[0.3cm] n\to n/8 :\quad T\left(n/8\right)=2T\left(n/16\right)+n/8-1 \end{array}\right.$$

This will be enough to make a hypothesis.

Then,

$$\boxed{T(n)=2^1\cdot T\left(\frac{n}{2^1}\right)+1\cdot n-\underbrace{1}_{=2^0}}\longrightarrow\\[0.3cm] T(n)=2\cdot\left(2\cdot T\left(\frac{n}{4}\right)+n/2-1\right)+1\cdot n-1=\\[0.3cm] =4\cdot T\left(\frac{n}{4}\right)+1\cdot n-2+1\cdot n-1\longrightarrow\\[0.3cm] \boxed{T(n)=2^2\cdot T\left(\frac{n}{2^2}\right)+2\cdot n-\left(2^0+2^1\right)}\\[0.3cm] T(n)=4\cdot\left(2\cdot T\left(\frac{n}{8}\right)+n/4-1\right)+2\cdot n-\left(1+2\right)=\\[0.3cm] =8\cdot T\left(\frac{n}{8}\right)+n-4+2\cdot n-\left(1+2\right)\longrightarrow\\[0.3cm] \boxed{T(n)=2^3\cdot T\left(\frac{n}{2^3}\right)+3\cdot n-\left(2^0+2^1+2^2\right)}\\[0.3cm] T(n)=8\cdot\left(2\cdot T\left(\frac{n}{16}\right)+n/8-1\right)+3\cdot n-\left(2^0+2^1+2^2\right)=\\[0.3cm] =16\cdot T\left(\frac{n}{16}\right)+n-8+3\cdot n-\left(2^0+2^1+2^2\right)\longrightarrow\\[0.3cm] \boxed{T(n)=2^4\cdot T\left(\frac{n}{2^4}\right)+4n-\left(2^0+2^1+2^2+2^3\right)}$$

Then,

$$T(n)=2^k\cdot T\left(\frac{n}{2^k}\right)+nk-\left(2^0+2^1+2^2+\ldots+2^{k-1}\right)$$

It remains to calculate the sum in brackets, which is a geometric sum with the following parameters: $a_1=1$ and $r=2$, then

$$2^0+2^1+2^2+\ldots+2^{k-1}=\frac{a_1\cdot\left(r^k-1\right)}{r-1}=\frac{2^k-1}{2-1}\longrightarrow\\[0.3cm] \boxed{2^0+2^1+2^2+\ldots+2^{k-1}=2^k-1}$$

Conclusion,

$$T(n)=2^k\cdot T\left(\frac{n}{2^k}\right)+nk-\left(2^k-1\right)$$

We use the initial condition :

$$\frac{n}{2^k}=1\to n=2^k\to\boxed{ k=\log_2n}$$

Then,

$$T(n)=\underbrace{2^{\log_2n}}_{=n}\cdot T(1)+n\cdot\log_2n-\left(\underbrace{2^{\log_2n}}_{=n}-1\right)\longrightarrow\\[0.3cm] T(n)=n\cdot1+n\cdot\log_2n-(n-1)\longrightarrow\\[0.3cm] \boxed{T(n)=n\cdot\log_2n+1+O\left(n\cdot\log_2n\right)}$$

ANSWER

$$T(n)=2T\left(n/2\right)+n-1\longrightarrow\\[0.3cm] T(n)=n\cdot\log_2n+1+O\left(n\cdot\log_2n\right)$$