# GATE2004-84

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

edited
0
Initial equation should be T(0)=1 not T(1) =1.
0
what role does the condition given play that n>=2 ?

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

Correct Answer: $A$

edited
2
How?
31

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

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 ?

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
11

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
0
@Ayush Can you provide me tutorial links for that method ??
0
Kenneth Rosen
0

@Ayush Upadhyaya how to get value of A1, A0 ? In your equation they are C and d.

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

@tusharp-Equate coefficients of n and constant term to 0.

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.

0
any one can tell me what is time complexity exist it  i.e. O(?)
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$$
4
nice trick :)
1
excellent trick bro
1
Smart method
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..
2

@Arjun

sir by applying muster theorem or subtract and conquer master theorem

ans comes out to be proportional to n*(2^n) .

Why it's far different from actual answer ?  Do muster theorem has any condition where it fails ?

Plz help.

1

EXCELLENT !!

Does this technique works for every recurrence relation ?

1
Yes, if options are given
0

@ same doubt do you got any answer?

0
Yeah , mine is same doubt, if you got any answer plz let me know.
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.
1
Nice reasoning for option C and D! Found useful!
0
Quickest way to solve this problem.

solution .

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

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.

edited
1
in eq 1 before (3) it will be $2^{n-3}$
0
Thanks, it was a typing mistake.
1
Thank you for a detailed explanation
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.

T(2) = 4.

Option A.

Solved under 30 seconds.

Hope this helps :)

## Related questions

1
6.9k views
The time complexity of the following C function is (assume $n > 0$) int recursive (int n) { if(n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); } $O(n)$ $O(n \log n)$ $O(n^2)$ $O(2^n)$
Let $A[1,\ldots,n]$ be an array storing a bit ($1$ or $0$) at each location, and $f(m)$ is a function whose time complexity is $\Theta(m)$. Consider the following program fragment written in a C like language: counter = 0; for (i=1; i<=n; i++) { if a[i] == 1) counter++; ... 0;} } The complexity of this program fragment is $\Omega(n^2)$ $\Omega (n\log n) \text{ and } O(n^2)$ $\Theta(n)$ $o(n)$
Let $G_1=(V,E_1)$ and $G_2 =(V,E_2)$ be connected graphs on the same vertex set $V$ with more than two vertices. If $G_1 \cap G_2= (V,E_1\cap E_2)$ is not a connected graph, then the graph $G_1\cup G_2=(V,E_1\cup E_2)$ cannot have a cut vertex must have a cycle must have a cut-edge (bridge) has chromatic number strictly greater than those of $G_1$ and $G_2$
Suppose we run Dijkstra’s single source shortest path algorithm on the following edge-weighted directed graph with vertex $P$ as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized? $P,Q,R,S,T,U$ $P,Q,R,U,S,T$ $P,Q,R,U,T,S$ $P,Q,T,R,U,S$