The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
247 views

Solve the recurrence equations:

  • $T(n) = T(n - 1)+ n$
  • $T(1) = 1$
asked in Algorithms by Veteran (42.7k points)
edited by | 247 views

2 Answers

+9 votes
Best answer

$T(n) = T(n-1)+n$
           $=T(n-2)+(n-1)+n$
           $=T(n-3)+(n-2)+(n-1)+n$
           $=T(n-3)+3n-(1+2)$
           .
           .
           .
           $=T(n-k)+kn-(1+2.....+(k-1))$   

$n-k=1$
$k=n-1$

$T(1)+(n-1)n-(1+2+3......+n-1-1)= 1+(n^2-n)- \frac{n(n+1)}{2} -2$
$\approx O(n^2)$

      

answered by Loyal (3.6k points)
edited by
T(n) = T(n-1)+n

          =T(n-2)+n-1+n

          =T(n-3)+n-2+n-1+n

            .

            .

            .

             .

T(n) = 1+2+3+4+5+6+7..........+(n-1)+n

        = n(n+1)/2
+2 votes

by using master theorm

answered by Veteran (12.4k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,017 questions
36,845 answers
91,385 comments
34,723 users