Answer to Question #224904 in Discrete Mathematics for Kavin

Question

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

Answer 1

Let's make a few substitutions to understand the properties of the desired sequence.

$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\\[0.3cm] n\to n/16 :\quad T\left(n/16\right)=2T\left(n/32\right)+n/16-1 \end{array}\right.$

To move forward, we need to understand how $T(n)$ is expressed through $T(n/2),\,\,\,T(n/4),\ldots$ Therefore,

$\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)}\\[0.3cm] T(n)=16\cdot\left(2\cdot T\left(\frac{n}{32}\right)+n/16-1\right)+4\cdot n-\left(2^0+2^1+2^2+2^3\right)=\\[0.3cm] =32\cdot T\left(\frac{n}{32}\right)+n-16+4\cdot n-\left(2^0+2^1+2^2+2^3\right)\longrightarrow\\[0.3cm] \boxed{T(n)=2^5\cdot T\left(\frac{n}{2^5}\right)+5n-\left(2^0+2^1+2^2+2^3+2^4\right)}\\[0.3cm]$

Making a proposal for a general formula :

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

It remains to calculate the sum in brackets, which is a geometric sum with the following parameters: $a_1=1$ , $r=2$ , the number of items in the sum $0\ldots(p-1)\to \text{Number}=p$ , then

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

Conclusion,

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

It remains to use the initial condition :

$\frac{n}{2^p}=1\to n=2^p\to\boxed{ p=\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)$