The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
2.7k views

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

evaluates to

  1. $2^{n+1} - n - 2$
  2. $2^n - n$
  3. $2^{n+1} - 2n - 2$
  4. $2^n + n $
asked in Algorithms by Veteran (69k points)
edited by | 2.7k views
Initial equation should be T(0)=1 not T(1) =1.

4 Answers

+35 votes
Best answer
$T(n) = 2T(n-1) +n, n \geqslant 2 , T(1) = 1$

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

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

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

           $=2^{n+1}-n -2$
answered by Boss (5.7k points)
edited by
How?

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

1.2 + 2.22 +3.23+.....+ (n-1).2n-1 let us say Sn.

Sn  =  1.2 + 2.22 +3.23+.....+ (n-1).2n-1

2.Sn =          1.22+2.23+.......+(n-2).2n-1+(n-1).2n

_                  _      _                  _                _

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

-Sn  =  2 + 22 +23 + .................+2n-1 -(n-1).2n

Sn =  n.2n-2n+1+2

 

 

I am stucked at this step ,plz clarify this 

T(n)=2kT(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 ?

saw the above comment?

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 ?

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

T(n)=n+2(n−1)+22(n−2)+⋯+2(n−1)(n−(n−1))  in second line it should be T(n-(n-1))??????????????

an additional 2^(n) term should also come

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

The given recurrence is

an = 2an-1 +n when n$\geq$2   .........................(1)

1 when n=1

The solution of an is given as

an= an H (Solution to homogenous part) + an (Particular solution)

anH will be given  as

$\alpha$(2)

anP 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

an = $\alpha$(2) -n-2

At n=1 an=1, so

we get $\alpha$ =2

so

an=2n+1-n-2

 

+41 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$$
answered by Veteran (346k points)
nice trick :)
excellent trick bro
Smart method
+7 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.
answered by Veteran (23.4k points)
+1 vote

solution .

answered by (245 points)
this is what i was looking for ,, thanx buddy :)
@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.
Yes @pramodborana112 u are right ,  it should be T(n-k) = 2T(n-(k+1)) + (n-k), but everything else are correct.


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,688 questions
40,231 answers
114,272 comments
38,803 users