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
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.
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 .😀
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 !
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😊.
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!
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
Hi sir , your videos are really great and helpful!!Thank you so much for them. I was having a doubt at the divide part at 6:03. can't we simply use the method provided in previous video,the method of " repeating the relation for k times and analysing at k= n"?i.e: We had the relation T(n)=T(n-1)+ n ----(1) if we replace by n-1, it becomes T(n-1)=T(n-2) +n-1 ----(2) putting back in (1), we get : T(n) =T(n-2) + 2n -1 -----(3) similarly we get T(n)=T(n-3) + 3n -2 similarly we get T(n)=T(n-4) + 4n -3 similarly we get ..... similarly we get ..... {for k times } similarly we get ..... similarly we get T (k) =T(n-k) +kn -(k-1) now assuming n=k, T(n) = T(0) + n^2 - n +1 => T(n) = 1 +n^2 -n +1 = n^2-n+2 => complexity is O(n^2) will it be wrong?
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.
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 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.
I need help understanding the part where you say that 1 is added in T(n) = 1 + n(n - 1)/2 because it is for the number of calls. What do you mean by number of calls?
Sir I watched this video today. I like the way you teach you cover math in algorithms that's the specialty. Now I understood why I learnt geometric series at school. Thank you sir.
Sir in loop,why we write n+1 and n? Also I am a bit confused in writing a recurrence relation whether n+1 or n. Sir kindly explain me in details. Thanks....
the loop runs n times but at last time n+1 it also checks if the condition is true or not , hence it takes CPU one extra cost to check loop last time ,even if body of loop is not executed....
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 .
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.
In the 'for' loop initialisation i = 0 takes constant time 1 and condition check, increment operation takes n times, so n+1 is for the 'for' loop alone and n is for the printf statement inside loop, so summing up loop parts only = n+1 + n = 2n +1 where the printf and condition check/increment operation both take n times so ....for asymptotic analysis 2n+1 can be reduced to n+1....also the outer guarding if statement has 1 time constant adding it up makes n+2 which again can be reduced to n or n+c where c doesn't matter in asymptotic Big O. That's why the in the final eqn 2n+2 is reduced to just n.
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.
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?
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..
So relatable 😂😅
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.
Before finding your videos, I was very scared of CSE subjects but now I m becoming hero in algorithms 👍
Did you got placed bro?
I have started admiring you Abdul !!! Wish every teacher/instructor be like you. Thank you
The way u have delivered it..... really made it very easy to understand.that is the beauty lies in this lecture.
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
Study is beautiful with u sir✌️👍🏻✌️
best algorithm teacher in the world
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.
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 .😀
Teaching is an art and abdul sir ,you are an artist of it. Cool, calm and composed teaching!!!!
kuch samjh nahi aaraha bro
\
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........
This is the best tutorial I have ever watch on youtube.
Yessss this is just what I needed. Thank you Prof Bari!
Thank you sir. Your videos will help me pass this examination. Thank you hundred-fold.
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 !
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😊.
When you said "Hello friends" at the beginning, I couldn't help but smile.
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
WOW three lectures I couldnt understand, then this guy comes along and I understand it in 3 minutes.
You have a natural way to explain these things. Exceptional videos. Would like to learn OS or python, java from you. Thank you.
This man's breathtaking!
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.
learning a lot from ur videos
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....
You deserve nothing but happiness and great things in your life! I cant thank you enough!
Recursive Tree Method 3:24
Substitution Method 7:47
note 1 9:16-9:49
note 2 13:39-13:48
Thnks bro🙂
Thank you!! Finally I got this, thanks to you!
Huge respect
To Bari sir, for deep knowledge.
Here he is! The man, the myth, the legend!
What a coincidence bhaiya!! I was also watching algorithm and you too
@@pratapujjwal4642 :D
Sir... You are a gem 💎 among teachers. Thanks🙏
It's my pleasure
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!
All colleges that teach data structures should fire their hopeless lecturers and just play this video. Immense respect for Abdul Bari
I thought you would slap me :p :p @ 8:54
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
Hi sir , your videos are really great and helpful!!Thank you so much for them.
I was having a doubt at the divide part at 6:03.
can't we simply use the method provided in previous video,the method of " repeating the relation for k times and analysing at k= n"?i.e:
We had the relation T(n)=T(n-1)+ n ----(1)
if we replace by n-1, it becomes T(n-1)=T(n-2) +n-1 ----(2)
putting back in (1), we get : T(n) =T(n-2) + 2n -1 -----(3)
similarly we get T(n)=T(n-3) + 3n -2
similarly we get T(n)=T(n-4) + 4n -3
similarly we get .....
similarly we get ..... {for k times }
similarly we get .....
similarly we get T (k) =T(n-k) +kn -(k-1)
now assuming n=k,
T(n) = T(0) + n^2 - n +1
=> T(n) = 1 +n^2 -n +1 = n^2-n+2
=> complexity is O(n^2)
will it be wrong?
its correct
Yes it's wrong. Try for T(n-5). It won't satisfy when u substitute k=5
Teaching is a talent and sir has done masters in it
In 1:03, why did we say n+1 for "for loop"?
Please make videos of computer architecture. You’re teaching skills is brilliant.
Should mention that 1 + 2 + 3 + .... n-1 + n is a summation that can be shorthanded to equal n(n+1)/2
Glad I saw that comment thanks buddy
You sir are a lifesaver
It’s a basic concept in math probably a 9th class kid knows it.
@@b088mohdzaid5 for people who haven’t been in math class for a long time, they can forget
Thanks for helping me obtain my degree :)
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.
He's staring that knowledge into my head
yes sir you teaching method is very good
Please continue publishing new tutorials on other CS courses like OS and etc. You are one of the best teachers i've ever seen.
really awesome explanation sir all software engineers
I appreciated the video a lot, thanks from Poland
Thank you sir
You helped me a lot.
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 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.
I need help understanding the part where you say that 1 is added in T(n) = 1 + n(n - 1)/2 because it is for the number of calls.
What do you mean by number of calls?
Oakland University Sent Me Here
Sir I watched this video today. I like the way you teach you cover math in algorithms that's the specialty. Now I understood why I learnt geometric series at school. Thank you sir.
14:13 Itna solve krne ke baad... Mahaul badal gya, zazbaat badal gye ;)
Sir in loop,why we write n+1 and n?
Also I am a bit confused in writing a recurrence relation whether n+1 or n.
Sir kindly explain me in details.
Thanks....
the loop runs n times but at last time n+1 it also checks if the condition is true or not , hence it takes CPU one extra cost to check loop last time ,even if body of loop is not executed....
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*
Your explanation is crystal clear, thanks a lot Sir for sharing your knowledge
thank you very much you help me to understand this, you are a legend
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.
Good to the the point lectures with such simplicity and examples... Amazing. may ALLAH bless you.
the best explanation ever. Thank you!
ENLIGHTENING 🙏💯🔥
God bless you! you made my life easy!!!!!
Kash mere class teacher bhi daa in sir ke jaise padha pate🤔🤗
Best lectures on Algorithms.
Why the kth equation is being taken like (n+1)+n???
Like we r already taking (n-(k-2)) then why??
Ok king I see you with the Tommy Hilfiger on 😍
love the random stares into the camera like at 8:48 :P
Thank you very much. You are a genius.
At 1:05 why sir has taken n+1 for , for loop?
if anyone knows then please do tell me.
In the 'for' loop initialisation i = 0 takes constant time 1 and condition check, increment operation takes n times, so n+1 is for the 'for' loop alone and n is for the printf statement inside loop, so summing up loop parts only = n+1 + n = 2n +1 where the printf and condition check/increment operation both take n times so ....for asymptotic analysis 2n+1 can be reduced to n+1....also the outer guarding if statement has 1 time constant adding it up makes n+2 which again can be reduced to n or n+c where c doesn't matter in asymptotic Big O.
That's why the in the final eqn 2n+2 is reduced to just n.
@@mahee96 🤝
you are teaching in nice way
Nicely Explained Professor!
Sir your lectures are very helpful for us.
Thank you sir
Roshni sharma nhạc hen ha chenhacchepp
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.
wow. I understand now! if I pass my final i will buy your sticker
thank you so much for posting this and all you clips. I found them very useful.
Life Saver.....
Thank you Sir.
Abdul Bari for President
I was going thorough your video lecture only
you're really good at teaching
Very Useful Series Sir. Thank you
Thank you so much sir you have helped me alot
Finally found a video shows how to solve this stupid recurrence problem.
thanks sir ur videos are so good really understood the concept
Thank you for your efforts
Sir!, Why do you ignore the if condition for the previous recursive relation sum?
Then why are you calculate the if condition for this sum?
It's may your wish ,it's doesn't affect the time complexity
You are amazing my friend a huge thank you!
best teacher ever
Thank you Abdul my prof is very bad at explaining, it like explaining the addition to a child using multiplication.
God bless you sir... you are a great teacher...
Nice video continue you are the best
Hello sir, T(0) would take "1" time, right? not "0" because the program still checks if 0 > 0 at the if-statement. at 6:00
I do also have the same doubt
a gold mine in youtube
Hello Sir,
Please recommend books or resources form where we can get exercises to solve these time related problems.
Thanks.