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
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 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.
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😊.
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, 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!
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 .
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....
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
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?
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.
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....👍
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.
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.
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.
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.
You considered the time taken by if statement in this function but you dud not consider the time taken by if statement in the previous lecture. Why is that so?
in the last video you ignored the time for condition check,but now it is included.Why? And how the time for the condition check will be one,I thing it have to be checked in all calls of the function.
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
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..
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 😂😅
Before finding your videos, I was very scared of CSE subjects but now I m becoming hero in algorithms 👍
Did you got placed bro?
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
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 🔥🔥🔥🔥
Study is beautiful with u sir✌️👍🏻✌️
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
Recursive Tree Method 3:24
Substitution Method 7:47
note 1 9:16-9:49
note 2 13:39-13:48
Thnks bro🙂
one of the best lecture on Algo... I HV ever listened........
Teaching is an art and abdul sir ,you are an artist of it. Cool, calm and composed teaching!!!!
kuch samjh nahi aaraha bro
\
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 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.
There should exist more people like you in the world! Thank you
This is the best tutorial I have ever watch on youtube.
You good sir have just expanded my brain and my wisdom, thanks for the great lessons!
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 !
Yessss this is just what I needed. Thank you Prof Bari!
When you said "Hello friends" at the beginning, I couldn't help but smile.
Thank you sir. Your videos will help me pass this examination. Thank you hundred-fold.
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.
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
learning a lot from ur videos
This man's breathtaking!
I thought you would slap me :p :p @ 8:54
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😊.
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.
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....
In 1:03, why did we say n+1 for "for loop"?
Thank you!! Finally I got this, thanks to you!
Sir... You are a gem 💎 among teachers. Thanks🙏
It's my pleasure
You deserve nothing but happiness and great things in your life! I cant thank you enough!
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
Huge respect
To Bari sir, for deep knowledge.
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
Here he is! The man, the myth, the legend!
What a coincidence bhaiya!! I was also watching algorithm and you too
@@pratapujjwal4642 :D
Teaching is a talent and sir has done masters in it
Thank you sir
You helped me a lot.
14:13 Itna solve krne ke baad... Mahaul badal gya, zazbaat badal gye ;)
yes sir you teaching method is very good
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!
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*
really awesome explanation sir all software engineers
Please make videos of computer architecture. You’re teaching skills is brilliant.
Thanks for helping me obtain my degree :)
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....
All colleges that teach data structures should fire their hopeless lecturers and just play this video. Immense respect for Abdul Bari
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
I appreciated the video a lot, thanks from Poland
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?
He's staring that knowledge into my head
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 🤝
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....👍
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.
Please continue publishing new tutorials on other CS courses like OS and etc. You are one of the best teachers i've ever seen.
Oakland University Sent Me Here
Kash mere class teacher bhi daa in sir ke jaise padha pate🤔🤗
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.
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 very much you help me to understand this, you are a legend
the best explanation ever. Thank you!
why is the for loop n+1 time at 1:06
We can ignore n+1 in for loop and add n in for loop derive the value like T(n)=T(n-1)+n check 2:30 mins
Your explanation is crystal clear, thanks a lot Sir for sharing your knowledge
God bless you! you made my life easy!!!!!
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
Thank you very much. You are a genius.
Sir your lectures are very helpful for us.
Thank you sir
Roshni sharma nhạc hen ha chenhacchepp
Why the kth equation is being taken like (n+1)+n???
Like we r already taking (n-(k-2)) then why??
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.
9:14 - Important note (why you should avoid adding expression)
Hello Sir,
Please recommend books or resources form where we can get exercises to solve these time related problems.
Thanks.
ENLIGHTENING 🙏💯🔥
Good to the the point lectures with such simplicity and examples... Amazing. may ALLAH bless you.
Nicely Explained Professor!
You considered the time taken by if statement in this function but you dud not consider the time taken by if statement in the previous lecture. Why is that so?
love the random stares into the camera like at 8:48 :P
Thank you so much sir you have helped me alot
thanks sir ur videos are so good really understood the concept
Best lectures on Algorithms.
Ok king I see you with the Tommy Hilfiger on 😍
can someone explain at 6:10 how does 1 + 2 +... + n - 1 + n = n(n+1)/2 // i understand the left side but i dont understand how he got the right side
15:00 why do we divide it by 2
in the last video you ignored the time for condition check,but now it is included.Why?
And how the time for the condition check will be one,I thing it have to be checked in all calls of the function.
Life Saver.....
Thank you Sir.
sir can we construct recurrence tree for the given recurrence relation without algorithm(void test(n))??
thank you so much for posting this and all you clips. I found them very useful.
muy buena explicación, ahora estoy suscrita..........
gracias
you're really good at teaching
you are teaching in nice way
Thanks Abdul Bari!
You are amazing my friend a huge thank you!
Mashallah... ❤❤❤
Sir please upload more videos about data structures sir it is very useful
God bless you sir... you are a great teacher...