2.1.2 Recurrence Relation (T(n)= T(n-1) + n) #2

Recurrence Relation for Decreasing Function
Example : T(n)= T(n-1) +n

Courses on Udemy
================
Java Programming

Data Structures using C and C++

C++ Programming

[emelyloria]

Teaching is a talent!! You're one of the best teachers I've known. I should have found your channel before.

[mmdarwani]

For Calculus, we have Prof. Leonard & for Algorithms, we have teacher Abdul Bari. Thank God

[michaelekoka]

Excellent teacher.

As he said, adding the n gives 2n-1, 3n-2, etc, making the pattern a bit less obvious and the expression a bit more difficult to solve. But sometimes we have to live dangerously, so here we go:

T(n) = T(n-1) + n
T(n) = T(n-2) + 2n - 1
T(n) = T(n-3) + 3n - 3
T(n) = T(n-4) + 4n - 6
...
T(n) = T(n-k) + kn - [(k-1) + (k-2) + ... + 3 + 2 + 1]

Assuming n-k = 0; k = n

T(n) = T(0) + n² - [(n-1) + (n-2) + ... + 3 + 2 + 1]

Isolating the expression in brackets
[(n-1) + (n-2) + ... + 2 + 1]

We know that
n + (n-1) + (n-2) + ... + 2 + 1 = n(n+1)/2

Taking off n from both sides we get
(n-1) + (n-2) + ... + 2 + 1 = (n(n+1)/2) - n

which resolves to
(n(n+1)/2) - 2n/2 => (n(n+1) - 2n)/2 => (n(n+1-2))/2 => n(n-1)/2

Plugging it back in the equation in its new form
T(n) = T(0) + n² - [n(n-1)/2]

Removing the brackets and swapping the sign
T(n) = T(0) + n² + n(1-n)/2
T(n) = 1 + (2n² + n(1-n))/2
T(n) = 1 + n(2n+1-n)/2
T(n) = 1 + n(n+1)/2

[Usertyspr]

Greatest teacher of Algorithms . Even my college teacher(dsa) first watchs your videos the he teaches us completely try to copy but couldn't .

[ravigupta]

Before finding your videos, I was very scared of CSE subjects but now I m becoming hero in algorithms 👍

[amberpradhan]

Hello Sir, You are the best teacher so far. God bless you and your family. Thank you for sharing your knowledge which is helping us a lot.

[sarfarazkhanbiradar]

I have started admiring you Abdul !!! Wish every teacher/instructor be like you. Thank you

[ishaqbhat]

The way u have delivered really made it very easy to understand.that is the beauty lies in this lecture.

[icepurple]

I have passed my data structures course by these lectures and now finally understanding algorithms. Thank you very much

[elitesquad]

Teaching is an ART and you are the ARTIST 🔥🔥🔥🔥

[SadiaAmin-uq]

Sir i took DAA course two times and failed both times and just couldn't understand this subject at all, i came across your playlist and it made my life so much easier. i thought i just couldn't understand this subject and felt really hopeless. thankyou so much for this amazing playlist, you are truly a gem.

[mahimsd]

one of the best lecture on Algo... I HV ever

[rathnaprabuayyappan]

Teaching is an art and abdul sir, you are an artist of it. Cool, calm and composed teaching!!!!

[priyankamanna]

Your teaching skill is super. I really understand each and every thing you taught and my concepts are really cleared out after watching this.. I hope you make more such video on programming concepts .😀

[erikadistefano]

There should exist more people like you in the world! Thank you <3

[ryzurrin]

You good sir have just expanded my brain and my wisdom, thanks for the great lessons!

[pedronieto]

Yessss this is just what I needed. Thank you Prof Bari!

[RKNancy]

Thank you sir. Your videos will help me pass this examination. Thank you hundred-fold.

[africanhope]

This is the best tutorial I have ever watch on youtube.

[Hoppensagen]

Should mention that 1 + 2 + 3 + .... n-1 + n is a summation that can be shorthanded to equal n(n+1)/2