Follow Us :

PA of Algorithms Q23

0. 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.
The order is

  • Option : A
  • Explanation :
    Given recurrence relation
    T(n)=T(n-1)+T(n-2)-T(n-3) n>3
       =n otherwise
    So we can write T(1)=1, T(2)=2 and T(3)=3 when n<=3
    Now, putting T=4 in the given equation we get,
    T(4)=T(3)+T(2)-T(1)
       =3+2-1=4
    Similarly, T(5)=T(4)+T(3)-T(2)
       =4+3-2=5
    and T(6)=T(5)+T(4)-T(3)=5+4-3=6;
    so in general,we get,T(n)=T(n-1)+T(n-2)-T(n-3)=(n-1)+(n-2)-(n-3)=n
    Therefore,T(n) = O(n)
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *