GATE CSE
First time here? Checkout the FAQ!
x
0 votes
137 views
asked in Algorithms by (375 points)   | 137 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 (65.9k 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 Apr 2017
  1. akash.dinkar12

    3514 Points

  2. Divya Bharti

    2546 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Shubham Sharma 2

    1610 Points

  7. Debashish Deka

    1588 Points

  8. Arunav Khare

    1454 Points

  9. Kapil

    1424 Points

  10. Arjun

    1420 Points

Monthly Topper: Rs. 500 gift card

22,076 questions
28,042 answers
63,233 comments
24,135 users