GATE CSE
First time here? Checkout the FAQ!
x
0 votes
148 views
asked in Algorithms by (495 points)   | 148 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 (66.7k 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 Jul 2017
  1. Bikram

    4894 Points

  2. manu00x

    2888 Points

  3. Debashish Deka

    1870 Points

  4. joshi_nitish

    1776 Points

  5. Arjun

    1496 Points

  6. Hemant Parihar

    1306 Points

  7. Shubhanshu

    1128 Points

  8. Arnab Bhadra

    1114 Points

  9. pawan kumarln

    1114 Points

  10. Ahwan

    940 Points


24,089 questions
31,062 answers
70,677 comments
29,400 users