Register

ISRO2018-37

• edited by
7,555 views
5 votes
5 votes

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)$
• edited by
User Avatar

3 Answers

13 votes
13 votes
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.
User Avatar
7 votes
7 votes
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
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

5 votes
5 votes
2 answers
1
Arjun asked Apr 22, 2018
4,622 views
ISRO2018-72
Consider the following C code segment int f(int x) { if(x<1) return 1; else return (if(x-1)+g(x)); } int g(int x) { if(x<2) return 2; else return (if(x-1)+g(x/2)); } Of the following, which best describes the growth of $f(x)$ as a function of $x$ ? Linear Exponential Quadratic Cubic
Consider the following C code segmentint f(int x) { if(x<1) return 1; else return (if(x-1)+g(x)); } int g(int x) { if(x<2) return 2; else return (if(x-1)+g(x/2)); }Of the...
User Avatar
3 votes
3 votes
4 answers
2
Arjun asked Apr 22, 2018
2,144 views
ISRO2018-56
The time complexity of computing the transitive closure of binary relation on a set of $n$ elements is known to be $O(n)$ $O(n*\log(n))$ $O(n^{\frac{3}{2}})$ $O(n^{3})$
The time complexity of computing the transitive closure of binary relation on a set of $n$ elements is known to be$O(n)$$O(n*\log(n))$$O(n^{\frac{3}{2}})$$O(n^{3})$
User Avatar
1 votes
1 votes
2 answers
3
Arjun asked Apr 22, 2018
4,158 views
ISRO2018-7
Assume $A$ and $B$ are non-zero positive integers. The following code segment: while(A!=B){ if*(A> B) A -= B; else B -= A; } cout<<A; // printing the value of A Computes the $LCM$ of two numbers Divides the larger number by the smaller number Computes the $GCD$ of two numbers Finds the smaller of two numbers
Assume $A$ and $B$ are non-zero positive integers. The following code segment:while(A!=B){ if*(A B) A -= B; else B -= A; } cout<<A; // printing the value of AComputes the...
User Avatar
1 votes
1 votes
1 answer
4
Arjun asked Apr 22, 2018
5,179 views
ISRO2018-12
An array $A$ consists of $n$ integers in locations $A[0], A[1], \ldots A[n-1]$. It is required to shift the elements of the array cyclically to the left by $k$ places, where $1<=k<=(n-1)$. An incomplete algorithm for doing this in linear time, without using another array is given ...
An array $A$ consists of $n$ integers in locations $A[0], A , \ldots A[n-1]$. It is required to shift the elements of the array cyclically to the left by $k$ places, wher...
User Avatar
Link Copied!