Dark Mode

vijju532
asked
in Algorithms
Jun 8, 2018

2,123 views
0 votes

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

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

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

= T(N-K) + 2N + 2(N-1)+2(N-2)+....+2(N-K+1)

= T(N-K)+2{ N + (N-1) + (N-2) + .....+ (N-K+1) } ------> A

We know that T(1)=1 ===> N-K=1 ===> K=N-1, SUBSTITUTING THIS VALUE IN **A**

= T(N-(N-1)) + 2 { N + (N-1) + (N-2) + .....+ (N-(N-1)+1) }

= T(1)+2 { N + (N-1) + (N-2) + .....+ (2) } ----> B , add +2 and -2 to B

= T(1)+2 { N + (N-1) + (N-2) + .....+ (2) } +2-2

= T(1)+2 { N + (N-1) + (N-2) + .....+ (2) +1 } -2 ---> Apply sum of first N natural numbers and T(1) = 1

= 1 + 2{$\frac{N (N+1)}{2}$} - 2

= N(N+1) -1