Question 132 – ISRO-2018
June 1, 2024Transactions
June 1, 2024Question 152 – ISRO-2018
The running time of an algorithm is given by
Then what should be the relation between T(1), T(2) and T(3), so that the order of the algorithm is constant?
Correct Answer: A
Question 69 Explanation:
T(n)= T(n-1) + T(n-2) – T(n-3)”
Solution:
Better way of solving is substitute.
T(1) = 1
T(2) = 2
T(3) = 3
T(4) = T(3) + T(2) – T(1) = 4
T(5) = T(4) + T(3) – T(2) = 5
:
:
T(n) = T(n-1) + T(n-2) – T(n-3) = n-1 + n-2 – n + 3 = n
So order is O(n)
Solution:
Better way of solving is substitute.
T(1) = 1
T(2) = 2
T(3) = 3
T(4) = T(3) + T(2) – T(1) = 4
T(5) = T(4) + T(3) – T(2) = 5
:
:
T(n) = T(n-1) + T(n-2) – T(n-3) = n-1 + n-2 – n + 3 = n
So order is O(n)
T(1) = T(2) = T(3)
T(1) + T(3) = 2 * T(2)
T(1) – T(3) = T(2)
T(1) + T(2) = T(3)