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

1 Answer

+1 vote
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 (64.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 ..:)
Members at the site
Top Users Feb 2017
  1. Arjun

    4680 Points

  2. Bikram

    4004 Points

  3. Habibkhan

    3738 Points

  4. Aboveallplayer

    2966 Points

  5. sriv_shubham

    2278 Points

  6. Smriti012

    2212 Points

  7. Arnabi

    1814 Points

  8. Debashish Deka

    1788 Points

  9. sh!va

    1444 Points

  10. mcjoshi

    1444 Points

Monthly Topper: Rs. 500 gift card

20,788 questions
25,938 answers
59,533 comments
21,926 users