ISRO CSE 2018 | Question: 37

Question

The running time of an algorithm is given by:

                      $T(n) = T(n-1) + T(n-2) - T(n-3)$, if $n > 3$

                                  = $n$, otherwise

Then what should be the relation between $T(1), T(2), T(3)$, so that the order of the algorithm is constant?

1. $T(1) = T(2) = T(3)$
2. $T(1) + T(3) = 2T(2)$
3. $T(1) - T(3) = T(2)$
4. $T(1) + T(2) = T(3)$

Comments

option B is correct.

---

Refer: https://gateoverflow.in/18927/the-running-time-of-an-algorithm-is-given-by-t-1-t-n-2-t-n-3-if-n%26gt

The above will give you a description that any value will give you a value of O(n)

 

This we will get any value as O(n) so all three T(1),T(2) and T(3) will have  O(n) so

 T(1)=T(2)=T(3)  as all will have o(n) only as that is the more concise answer

SO OPTION A IS CORRECT

 

---

Ans

Answer 1

For sufficiently large $n$,

$T(n) = Tn-1)+T(n-2) - T(n-3).$

If the order of the algorithm for which above recurrence is applicable for the time complexity, is a constant,

$T(n) = T(n-1)$.

$\implies T(n) = T(n) + T(n-2) - T(n-3)$

$\implies T(n-2) = T(n-3)$

Going like this, we must have $T(1) = T(2) = T(3)$ which is option A.

PS: Typo is obvious in the question.

Comments

Sir, where is typo.. I didnt understand

---

SIr can you explain what's the problem in this question and what is the correct solution

---

Why are we considering sufficiently large $n$ when we have to find relation between $T(1)$, $T(2)$ and $T(3)$? Doesn't the base condition says $T(n) = n$ when $n\ngtr 3$>?

Answer 2

T(n)=T(n-1)+T(n-2)-T(n-3) , n>3

else T(n)=n

T(1)=1

T(2)=2

T(3)=3

using option:-

A. false

B. 1*3 is not equal to 4

C. T(1)-T(3)=> 1-3= -2 not equal to 2

D. 1+2=3 i,e equal to T(3)

ans . is D

Comments

I thought B and D are correct.

B. 1+3=2×2
D. 1+2=3

But reading the question again, t1 t2 t3 are equal as all of them will be of the order of O(1) . We dont have to take their values literally.

---

@sonveer tomar 1,Consider for urself when all the options are solved by substituting the values we have the following answer:-

For option  b)

1+3=2*2

For option c)

1-3=2

For option d) 1+2=3

3=3. Now you tell why option d) is not right?It is also giving a constant value as answer

Answer 3

Ans: D

 

Refer: https://gateoverflow.in/18927/the-running-time-of-an-algorithm-is-given-by-t-1-t-n-2-t-n-3-if-n%26gt

Answer 4

Ans

Answer 5

This is actually a very elegant recurrence.

T(n)=T(n−1)+T(n−2)−T(n−3)

 

For constant time complexity, we want:

                        T(n)=c

for all n.

 

So let's force the recurrence to produce a constant.

Let's Assume:

                T(n−1)=T(n−2)=T(n−3)=c

Then

                T(n)= c+c−c = c

We got it! The constant continues forever.

 

Hence we need the initial values to be equal:

                 T(1)=T(2)=T(3)