The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+22 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 $

+38 votes

Best answer

+17

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

+1

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

+4

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

+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$$

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$$

+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.

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

Hence option A is ans.

+4 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.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,871 questions

47,531 answers

146,039 comments

62,297 users