2.1.2 Recurrence Relation (T(n)= T(n-1) + n) #2
Vložit
- čas přidán 22. 01. 2018
- Recurrence Relation for Decreasing Function
Example : T(n)= T(n-1) +n
Courses on Udemy
================
Java Programming
www.udemy.com/course/java-se-...
Data Structures using C and C++
www.udemy.com/course/datastru...
C++ Programming
www.udemy.com/course/cpp-deep...
For Calculus, we have Prof. Leonard & for Algorithms, we have teacher Abdul Bari. Thank God
Indeed. Haha.
For linear algebra we have Gilbert Strang.
🙂🙂
Prof. Leonard saved my undergrad calculus!!!
Do you have recommendations for Physics (1&2) and Circuit classes? I CANNOT deal with these..
Teaching is a talent!! You're one of the best teachers I've known. I should have found your channel before.
I wish I had found this channel before I took algorithms. I would have aced everything :)
mw too
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
its T(n) = T(n-3)+3n-3
I think
@@ajaypanthagani5959 Sequence is indeed 1 3 6 10... Good catch, thanks!
I would like to ask, where did 2n^2 came from after removing and swapping the sign? did you just plugged in a constant c to get n(n+1)/2?
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.
I have started admiring you Abdul !!! Wish every teacher/instructor be like you. Thank you
Greatest teacher of Algorithms . Even my college teacher(dsa) first watchs your videos the he teaches us .....He completely try to copy but couldn't .
unique art of abdul bari sir..
Study is beautiful with u sir✌️👍🏻✌️
Before finding your videos, I was very scared of CSE subjects but now I m becoming hero in algorithms 👍
Did you got placed bro?
Teaching is an ART and you are the ARTIST 🔥🔥🔥🔥
I have passed my data structures course by these lectures and now finally understanding algorithms. Thank you very much
best algorithm teacher in the world
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 .😀
There should exist more people like you in the world! Thank you
You good sir have just expanded my brain and my wisdom, thanks for the great lessons!
one of the best lecture on Algo... I HV ever listened........
8:50 when you go to office hours and the professor has already explained it twice and you say: I still don’t get it professor.
The way u have delivered it..... really made it very easy to understand.that is the beauty lies in this lecture.
When you said "Hello friends" at the beginning, I couldn't help but smile.
You have a natural way to explain these things. Exceptional videos. Would like to learn OS or python, java from you. Thank you.
Sir, loves your videos! Finally i can understand Algorithms in a simple way. Please continue to create more videos! Hope u can cover every Advanced Algorithms as in Cormen’s textbook.Thanks!
Yessss this is just what I needed. Thank you Prof Bari!
I thought you would slap me :p :p @ 8:54
Sir you are very accurate and to the point, and also I love to watch your videos as you are accurate with your way of teaching....
WOW three lectures I couldnt understand, then this guy comes along and I understand it in 3 minutes.
This is the best tutorial I have ever watch on youtube.
This man's breathtaking!
Thank you sir. Your videos will help me pass this examination. Thank you hundred-fold.
learning a lot from ur videos
Sir the way you teach every concept get's clear.....thanks a lot sir you are making future of many students bright...keep going sir
He's staring that knowledge into my head
Thank you!! Finally I got this, thanks to you!
thank you so much for posting this and all you clips. I found them very useful.
Sir you are awesome and teaching style is very good. Thanks for this video Sir. Now I can easily understand everything things about algorithm. Again thank you sir. May you live long and healthy.
You deserve nothing but happiness and great things in your life! I cant thank you enough!
Thank you sir...tomorrow is our exam and your lectures are ssly a saviour for us.....it easily made us understand the concept one night before the exam....👍
sir you are best, with best explanation i got till now. i was never understanding these algorithms because nobody actually knew it completely and never explained them fully. so i always cramed them , which i never like😂. Thank you a lot for keeping and incresing my interest in programming😊.
Thank you sir
You helped me a lot.
Teaching is an art and abdul sir ,you are an artist of it. Cool, calm and composed teaching!!!!
kuch samjh nahi aaraha bro
\
Your explanation is crystal clear, thanks a lot Sir for sharing your knowledge
the best explanation ever. Thank you!
You are amazing my friend a huge thank you!
I appreciated the video a lot, thanks from Poland
Oakland University Sent Me Here
Sir ,,,you are great ,I love the way you teach. It is so clear.Thanks a lot sir.NPTEL teachers are so boring ,,,,,,but you are interesting with your subject.
Thank you! This video helped me a lot!
Huge respect
To Bari sir, for deep knowledge.
Life Saver.....
Thank you Sir.
God bless you sir... you are a great teacher...
Blessed Explanation !
love you sir ! great explanation
That was indeed simple. Thank you
Nice video continue you are the best
ENLIGHTENING 🙏💯🔥
Nicely Explained Professor!
Very Useful Series Sir. Thank you
best teacher ever:-)
Sir... You are a gem 💎 among teachers. Thanks🙏
It's my pleasure
This guy good for real..😁
Thank you so much sir you have helped me alot
really awesome explanation sir all software engineers
thanks sir ur videos are so good really understood the concept
Thanks for helping me obtain my degree :)
Here he is! The man, the myth, the legend!
What a coincidence bhaiya!! I was also watching algorithm and you too
@@pratapujjwal4642 :D
you're really good at teaching
thank you very much you help me to understand this, you are a legend
All colleges that teach data structures should fire their hopeless lecturers and just play this video. Immense respect for Abdul Bari
Best lectures on Algorithms.
جزاكَ الله خيرًا
Thanks a lot sir, loads of respect
Please make videos of computer architecture. You’re teaching skills is brilliant.
Recursive Tree Method 3:24
Substitution Method 7:47
note 1 9:16-9:49
note 2 13:39-13:48
Thnks bro🙂
love the random stares into the camera like at 8:48 :P
Please continue publishing new tutorials on other CS courses like OS and etc. You are one of the best teachers i've ever seen.
Abdul Bari for President
Good to the the point lectures with such simplicity and examples... Amazing. may ALLAH bless you.
you are amazing sir , tysm
14:13 Itna solve krne ke baad... Mahaul badal gya, zazbaat badal gye ;)
Sir please upload more videos about data structures sir it is very useful
Thanks Abdul Bari!
Thank you very much. You are a genius.
Hello Friends!
Kash mere class teacher bhi daa in sir ke jaise padha pate🤔🤗
yes sir you teaching method is very good
God bless you! you made my life easy!!!!!
best teacher ever
Sir your lectures are very helpful for us.
Thank you sir
Roshni sharma nhạc hen ha chenhacchepp
I really initially thought that the answer should be O(n) as there is one for loop. I was clearly wrong. Thank you sir for explaining this soo elegantly and making us better students
Nice explanation sir !
In fields where legends freely roam,
A GOAT emerges, to claim its throne.
With prowess unmatched, it scales the height,
In realms of glory, it takes its flight.
In games of skill, it reigns supreme,
The GOAT, a champion in every scheme.
With grace and power, it dominates,
In history's annals, it seals its fate.
Through trials faced and challenges met,
The GOAT's legacy, we won't forget.
In every triumph, it leaves its mark,
A symbol of greatness, shining stark.
Oh, GOAT, in realms of fame you dwell,
Your spirit shines, a timeless spell.
In every field, your legend's told,
Greatest Of All Time, forever bold.
Excellent Teacher...
you are teaching in nice way
very useful lectures
Thanks sir
a gold mine in youtube
Excellent teaching
sir can we construct recurrence tree for the given recurrence relation without algorithm(void test(n))??
A probable rectification - Since T(0) is never written as 0 as instructed by you in the previous video , T(0) in the execution depiction should be equal to 1not 0. So it should be 1+2+3+......+ n-1+n = n(n-1)/2 .
n(n+1)/2*
Sir, ar 5:51 you took T(0) will take 0 time. But you also said that 0 time means constant time so we take 1 instead of 0.
So, for summing up, if taken 1 instead of 0 sum should be = n(n+1)/2 +1 .
I know it wont make a difference in the final answer but just wanted to confirm if I am theoritically correct or not ?
Please do reply and Thank you in advance !
fantastic explanation sir
8:49
:P :P
Sir please....upload a video on PROPERTIES OF ASYMPTOTIC NOTATIONS and how they are used....lately i have beem getting confused on that topic...sir please it will be very helpful for us in GATE examination.