GATE CSE
First time here? Checkout the FAQ!
x
0 votes
160 views asked in Algorithms by Junior (581 points)   | 160 views

1 Answer

+2 votes
Best answer
This is a simple question @Himanshu :)

Given , T(n) = T(n-1) + c

      ⇒   T(n) = (T(n-2) + c) + c [We substitute for T(n-1) similarly here]

      ⇒   T(n)  = (T(n-3) + c) + c + c = T(n-3) + 3c

     .

     .

      ⇒   T(n)  = T(n-n) + nc = T(0) + nc

     Considering T(0) = some constant , we have

     T(n)  =  nc  = O(n)
answered by Veteran (76.8k points)  
selected by
Ya i know its very simple but its my first time i m doing these type of questions never did that so its not simple for me but anyway thanks a lot @habibkhan :)
Ok @Himanshu bro..Its fine..Most welcome ..:)


Top Users Sep 2017
  1. Habibkhan

    6826 Points

  2. Arjun

    2310 Points

  3. Warrior

    2302 Points

  4. nikunj

    1980 Points

  5. A_i_$_h

    1922 Points

  6. manu00x

    1750 Points

  7. rishu_darkshadow

    1744 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,033 questions
33,618 answers
79,661 comments
31,066 users