The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
3.6k 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 (59.6k points)
edited by | 3.6k views
0
Initial equation should be T(0)=1 not T(1) =1.

4 Answers

+38 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 Loyal (5.7k points)
edited by
+2
How?
+17

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

+1

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 ?

0
saw the above comment?
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

0

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))??????????????

0
an additional 2^(n) term should also come
+4

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

0
Why havent the leaf nodes been calculated into the total cost? They will incurr 2^n cost
0
Thank you
+48 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 (359k points)
+2
nice trick :)
0
excellent trick bro
0
Smart method
+9 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 Boss (22.9k points)
+4 votes

solution .

answered by (251 points)
+1
this is what i was looking for ,, thanx buddy :)
+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.
0
Yes @pramodborana112 u are right ,  it should be T(n-k) = 2T(n-(k+1)) + (n-k), but everything else are correct.
0
I think  there would be change in arithmetric geometric expression  then as k =n-2 then in that case  how would we solve


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

40,871 questions
47,531 answers
146,039 comments
62,297 users