33 votes

The recurrence equation

$ T(1) = 1$

$T(n) = 2T(n-1) + n, n \geq 2$

evaluates to

- $2^{n+1} - n - 2$
- $2^n - n$
- $2^{n+1} - 2n - 2$
- $2^n + n $

50 votes

Best answer

36

Here everything is straight forward, the only complex thing is evaluation of

1.2 + 2.2^{2} +3.2^{3}+.....+ (n-1).2^{n-1} let us say S_{n}.

S_{n} = 1.2 + 2.2^{2} +3.2^{3}+.....+ (n-1).2^{n-1}

2.S_{n }= 1.2^{2}+2.2^{3}+.......+(n-2).2^{n-1}+(n-1).2^{n }

_ _ _ _ _

.................................................................................................

-S_{n} = 2 + 2^{2 }+2^{3} + .................+2^{n-1} -(n-1).2^{n}

S_{n} = n.2^{n}-2^{n+1}+2

2

I am stucked at this step ,plz clarify this

T(n)=2^{k}T(n-k)+2^{(k-1)}T(n-(k-1))+2^{(k-2)}T(n-(k-2))+...........+n

Now k=n-1 ,so

T(n)=2^{(n-1)}+2^{(n-2)}(2)+2^{(n-3)}(3)+...........+n

Now how to proceed from here ?

0

In above comments series formed is of the form 1.2 + 2.22 +3.23+.....+ (n-1).2n-1

While I am getting 2^n(1/2+2/4+3/8+.........)+n ,so how is it same ?

–1

I was stuck at the same point , just multiply **Sn (sumation) ** with 2 and then subtract it with the original **Sn.**This will create a geometric series of 2s +(-n). The sumation of geometric series turns out to be 2^n+1 - 2. Hence final answer is A

13

We can solve it using recurrence relation method that we used to do in discrete mathematics

The given recurrence is

**a**_{n} = 2a_{n-1 }+n when n$\geq$2 .........................(1)

1 when n=1

The solution of a_{n} is given as

a_{n}= a_{n} ^{H} (Solution to homogenous part) + a_{n}^{P } (Particular solution)

a_{n}^{H} will be given as

$\alpha$(2)^{n }

a_{n}^{P} will be in form Cn +d

Substituting this in (1) we get

Cn+d = 2Cn+n+2d-2c

n(C+1) + (d-2C) =0

C=-1 and d=-2.

So our recurrence becomes

a_{n} = $\alpha$(2)^{n } -n-2

At n=1 a_{n}=1, so

we get $\alpha$ =2

so

a_{n}=2^{n+1}-n-2

0

n(C+1) + (d-2C) =0

How did you calculate C and d after this ? @Ayush Upadhyaya

might b silly but m stuck here. Plz help bro

1

One simple way to answer such question is:

**put n=2 ( any small case and find its value and put in all the equations )**

T(1) = 1

**T(2) = 4**

T(3) = 11

*option a) 4*

option b) 2

option c) 2

option d) 6

Now when we put n=2 in the equations we get the correct answer only in **option a**.

If multiple eq gives the correct answer then we have to take other case and check again on the remaining equations which were giving the correct answer.

Please correct me if this approach is wrong.

78 votes

T(1) = 1

T(2) = 4

T(3) = 11

T(4) = 26

T(5) = 57

T(6) = 120

T(7) = 247

So, $$T(n) = 2^{n+1} - n - 2$$

T(2) = 4

T(3) = 11

T(4) = 26

T(5) = 57

T(6) = 120

T(7) = 247

So, $$T(n) = 2^{n+1} - n - 2$$

2

is it required that we go till 7 value i put n=2 and get 4 then check ans which gave me 4 by putting n=2 only A option satisfied it..

22 votes

Given that T(1) =1 //OMG here itself Option C & D fails now check A & B

T(2)=2T(1)+n=2+2=4 //Option B evaluates to 2 so it is wrong

Hence option A is ans.

T(2)=2T(1)+n=2+2=4 //Option B evaluates to 2 so it is wrong

Hence option A is ans.

9 votes

1

@varun singh

you have written

T(n-k) = 2T(n-(k-1)) + (n-k)

so for k=2

T(n-2) = 2T(n-(2-1)) + (n-2)

T(n-2) = 2T(n-1) + (n-2)

so it should be

T(n-k) = 2T(n-(k+1)) + (n-k)

please look into it and if i am wrong please do correct me.

you have written

T(n-k) = 2T(n-(k-1)) + (n-k)

so for k=2

T(n-2) = 2T(n-(2-1)) + (n-2)

T(n-2) = 2T(n-1) + (n-2)

so it should be

T(n-k) = 2T(n-(k+1)) + (n-k)

please look into it and if i am wrong please do correct me.

3 votes

Here, $T(1)=1$ and

$\begin{align} T(n)&=2T(n-1)+n\\&=2^2T(n-2)+2(n-1)+n;~[\text{Putting }T(n-1)=2T(n-2)+(n-1)]\\&=2^3T(n-3)+2^2(n-2)+2(n-1)+n;~[\text{Doing so}]\\&=\cdots\\&=2^{n-1}T(n-(n-1))+2^{n-2}\{n-(n-2)\}+2^{n-3}\{n-(n-3)\}+\cdots+2(n-1)+n\\&=2^{n-1}T(1)+2^{n-2}(2)+2^{n-3}(3)+\cdots+2^{1}(n-1)+2^{0}n\end{align}$

Now putting $T(1)=1$ as given,

$\begin{align}\therefore T(n)&=2^{n-1}(1)+2^{n-2}(2)+2^{n-3}(3)+\cdots+2^{1}(n-1)+2^{0}n \tag{i} \\ \Rightarrow 2T(n)&=2^n(1)+2^{n-1}(2)+2^{n-2}(3)+\cdots+2^2(n-1)+2^{1}n \tag{ii}\end{align} $

$\mathrm{no(ii)}-\mathrm{no(i)}\Rightarrow\\ \begin{align}T(n)&=2^n+2^{n-1}(2-1)+2^{n-2}(3-2)+\cdots+2^1(n-(n-1))-2^{0}n\\&=(2^{n}+2^{n-1}+2^{n-2}+\cdots+2)-n\\&=(2+2^2+2^3+\cdots+2^{n-1}+2^n)-n; ~[\text{Rearranging}]\\&=\frac{2(2^n-1)}{2-1}-n;~[\scriptsize\because a+ar+ar^2+\cdots+ar^n=\frac{a(r^{n+1}-1)}{r-1}\text{ as Geometric Series}]\\&=2^{n+1}-2-n \end{align}$

$\therefore T(n)=2^{n+1}-n-2$.

So the correct answer is **A**.

1 vote

One simple way to answer such question is:

**put n=2 ( any small case and find its value and put in all the equations )**

T(1) = 1

**T(2) = 4**

T(3) = 11

*option a) 4*

option b) 2

option c) 2

option d) 6

Now when we put n=2 in the equations we get the correct answer only in **option a**.

If multiple eq gives the correct answer then we have to take other case and check again on the remaining equations which were giving the correct answer.

0 votes

0

And just for extra purpose. What’s it’s time complexity? for me it’s coming O(n*2^n) using muster theorem. Please help. @immanujs

0

Using Substitution method, you will get $O(2^n)$

reference : https://gateoverflow.in/19033/t-c-of-t-n-2t-n-1-n-n-1-t-1-1

1

I will try doing it using substitution method. You please consider trying with muster theorem too.

Thanks for reference, I understood. O(n*2^n) is correct by s&c and substitution gives O(2^n).

Thanks for reference, I understood. O(n*2^n) is correct by s&c and substitution gives O(2^n).

0

i used Master theorem only when recurrence eq. are in the form of $T(n)=aT(n/b)+Θ(n^k log^p n)$

I wrote about this here : https://www.bitsofcs.xyz/2020/10/master-theorem-recurrence-relations.html

and for the other form T(n) = T(n-k) + c Substitution method is good.

read here : https://www.bitsofcs.xyz/2020/09/recurrence-relation-recurrence-relation.html