Solution to Solve the recurrence by substitution method. T(n) = 2T (n/2)+n-1 and T (1) =1. - Sikademy
Author Image

Archangel Macsika

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

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

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)

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-2718-qpid-1188