The running time of an algorithm is given by T(n) = T(n-1) + T(n-2) — T(n-3),…

2018

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) and T(3), so that the order of the algorithm is constant ?

  1. A.

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

  2. B.

    T(1) + T(3) = 2 * T(2)

  3. C.

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

  4. D.

    None of these

Attempted by 82 students.

Show answer & explanation

Correct answer: A

To determine the order of the algorithm, we analyze the recurrence relation T(n) = T(n-1) + T(n-2) - T(n-3). The characteristic equation is r^3 - r^2 - r + 1 = 0, which factors to (r-1)^2(r+1) = 0. The roots are r=1 (multiplicity 2) and r=-1. The general solution is T(n) = A + Bn + C(-1)^n. For the time complexity to be constant O(1), the coefficient B of the linear term n must be zero. This condition is satisfied when T(1) = T(2) = T(3), which corresponds to Option A.

Explore the full course: Isro