The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

+35 votes

Best answer

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

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 ?

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 ?

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

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

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

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

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

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

Hence option A is ans.

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 279
- Exam Queries 396
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 7

33,688 questions

40,231 answers

114,272 comments

38,803 users