Difficulty increases by each video. When I get stuck I refer previous videos in the playlist. Very nicely you have ordered the playlist till now. Thank you again sir.
Saved me 3 years ago as I was getting my bachelor's in computer science and here u are again sir saving me again as I'm getting a bachelor's in software engineering.
Guys, I finally found out why he wrote ( (2^(k+1)) -1 ), instead of (2^k)-1. So, let me make is as simple as possible, because I was also stuck on this very simple doubt for 2 hrs. If we all got a doubt here, it clearly means that we did not count the number of terms. Let's take 2 cases first. See this -> 2^(n-1) + 2^(n-2)+ . . . . . . . . + 2^(2) + 2^(1) + 2^(0). This GP is from 0 to n-1, now, If i tell you to count from 0 to n-1 where n=4, you would totally count 4 digits. That is 0 1 2 3. So there are 4 terms. Just like that for the above equation that I wrote, we have n terms. So, now let's use that general GP formula that we all know about, that is a(r^k -1)/(r-1). You will get 2^n-1 as answer. BUT, BUT, BUT, We all want to know why on earth we all got 2^(k+1) - 1 right. It's really simple. Just like I told you that there are 2 cases. The 1st case was the first equation that I asked you guys to count. Now, I will give you guys another equation as case 2. This equation is the same equation that we will get exactly @10.06 which is 2^n + 2^(n-1) + 2^(n-2) + . . . . . . . . . + 2^0. Now look at this equation really carefully and try to count how many terms there are in this equation. It goes from 0 to n, and not from 0 to n-1(just like in case 1). So let me ask you something, if I asked you to count from 0 to n, instead of n-1, where n=4, you will count 5 terms, that is 0 1 2 3 4. which is n+1 and not n. NOW YOU GOT IT??. in case 2, you can see that there is a an extra term called 2^n. That is the reason we take from 0 to n, instead of 0 to n-1. Instead of just writing this as the next step of the GP equation substitution, he directly wrote it as ( (2^(k+1)) -1 ). That was why we got confused. I really hope this helped everything, as This took about 2 hrs. for me to find and come up with a explanation this detailed.
I am new to your channel, just watched a couple of videos, and am totally hooked. The quality and depth are superb. Subscribing to your channel, and heartful gratitude for putting out such amazing videos. Thank you!
Dear Abdul Bari sir, how you keep track of all these information in ur brain? my brain is already rebooting and I am only half way through your playlist. I just want to let you know that this playlist was really helpful. I might not get a good grade in algorithm but I have surely learned better and thank you for that
Hello sir, I was wondering, isn't the sum of a gp series have the formula- Sum= a((r^n)-1)/r-1 I see you used r to the power of n+1? Is it a special case here?
Interesting to note in all 3 previous videos, the substitution method (counting number of calls) produced a result 1 more than recurrence tree (counting number of prints) method. However in this example of 2T(n-1), these 2 methods both give 2^(n+1)-1. I guess this is because now, the tree method was also counting all the 2^k leaves of T(0), whereas previous videos never counted T(0) in tree method?
2^n + 2^n = 2^(n+1) Reason: Let n = 2 2*2 + 2*2 We have 2*2 two times 2*2*2 the last 2 is 1 in (n+1) We are duplicating the 2*2 to give us 2*2+2*2 Note: the base 2 is important as if it was 3 then we would have triplicate the product of power. let n = 2 3^n + 3^n 3*2 + 3*2 = 3^(2+1) (3*3) + (3*3) + (3*3) = 3*3*3
this is not exactly what is shown in the video ,,actually the obtained series was 1+2+2^2+2^3+2^4+....+2^k and this forms a Gp series ..and sir has clearly shown in the video how to calculate it..
I am having some doubt regarding sum of the geometric mean 5:35 Sum of a GP is a(r^k -1)/r-1 and not a(r^(k+1) -1)/r-1. Where did that k+1 term came from? It would be really helpfull if someone replies
Look at the number of terms. They're starting from a*r^0 and going upto a*r^k, hence, k+1 terms and a(r^(k+1) -1)/r-1. Had it been starting from a*r^1, it would have been a(r^k-1)/r-1.
In above when 2^n T(0) + 1+2+2²+......+2^n-1 Here when we put the value of n so that T(n) become T(0) so as 2^n should become 2⁰ . . . 2^n + 2^n -1 = 2⁰ + 2⁰ -1 = 1+1-1= 1 Hence, T(n)= 1 Sir give me some thoughts
Sir in the recurrence tree you made I think the tree should be ended with leaf nodes T(n-k) and not T(0) after tracing it for k steps. Though the tree wouldn't be complete if it is further traceable so we will trace it for n steps and hence summation of all those terms will be taken for n steps and which is how we will get the function T(n)=2^(n+1)-1
Hello sir, in 10.03 you substitute the geometric series formula as (2^k)-1, but in 5.31 when you write the formula isn't it suppose to be ( (2^k)-1/(r-1) ) instead you wrote ( (a(r^(k+1)) -1)/(r-1) ) and so in 4.58 you wrote ( (2^(k+1)) -1 ). May i know why you write k+1 in here instead of k only?
I was quite confused about this too. According to the formula I know for the sum of gp series would be (2^k)-1/2-1. Not quite sure why its different here
Guys, I finally found out why he wrote ( (2^(k+1)) -1 ), instead of (2^k)-1. So, let me make is as simple as possible, because I was also stuck on this very simple doubt for 2 hrs. If we all got a doubt here, it clearly means that we did not count the number of terms. Let's take 2 cases first. See this -> 2^(n-1) + 2^(n-2)+ . . . . . . . . + 2^(2) + 2^(1) + 2^(0). This GP is from 0 to n-1, now, If i tell you to count from 0 to n-1 where n=4, you would totally count 4 digits. That is 0 1 2 3. So there are 4 terms. Just like that for the above equation that I wrote, we have n terms. So, now let's use that general GP formula that we all know about, that is a(r^k -1)/(r-1). You will get 2^n-1 as answer. BUT, BUT, BUT, We all want to know why on earth we all got 2^(k+1) - 1 right. It's really simple. Just like I told you that there are 2 cases. The 1st case was the first equation that I asked you guys to count. Now, I will give you guys another equation as case 2. This equation is the same equation that we will get exactly @10.06 which is 2^n + 2^(n-1) + 2^(n-2) + . . . . . . . . . + 2^0. Now look at this equation really carefully and try to count how many terms there are in this equation. It goes from 0 to n, and not from 0 to n-1(just like in case 1). So let me ask you something, if I asked you to count from 0 to n, instead of n-1, where n=4, you will count 5 terms, that is 0 1 2 3 4. which is n+1 and not n. NOW YOU GOT IT??. in case 2, you can see that there is a an extra term called 2^n. That is the reason we take from 0 to n, instead of 0 to n-1. Instead of just writing this as the next step of the GP equation substitution, he directly wrote it as ( (2^(k+1)) -1 ). That was why we got confused. I really hope this helped everything, as This took about 2 hrs. for me to find and come up with a explanation this detailed.
we are not taking the frequency of the statement, instead we are taking the amount of time that is required for that statement to run just one time, that is "1".
Hi, can you provide an answer for T(n-1) + T(n-2) + 1? I know for a fact that it is O(2^n) But how do you expand this using iteration method? Thank you.
You are gem sir.
correct
misunderstood(gemitaiz)
Pro trick : you can watch series on Flixzone. Been using them for watching loads of movies lately.
@Rhett Kaison Yup, been using flixzone for months myself =)
i would never understand DAA if you weren't here in this planet. Love you Abdul sir. And yes, we want more Abduls like you !
planets["Sol III"].deployEntity("Abdul Bari, rand(100,100000))
agree, so glad we are in the same universe
@@babitaburnwal7929 language?
Finished this video and with this, finished my daily task of watching 3-4 videos from this playlist.
For anyone who's confused at 10:16, here is the answer
that 2ⁿ+2ⁿ= 2(2ⁿ) = (2¹) (2ⁿ) = (2ⁿ⁺¹)
how 2^k-1 ? at above step at 10:10
@@vansh6183 1+2+...+2^(k-1) is an algebraic summation which id equal to 2^k -1
for anyone who is confused at this comment, don't worry confusion is universal
i was confused but its a little mistake made by me, sir did the correct sollution
Anyone watching in 2024 ? 🙃
Exams
😂😅
yes bro starting from today and its 22 videos have been done
Yes.. 🦤
Yes 🐧
You are a much better professor than the one I pay too much money for. Thank you for this wonderful series of videos.
1:46 Recursive Tree Method
5:05 note 1_
6:42 Substitution Method
Difficulty increases by each video. When I get stuck I refer previous videos in the playlist. Very nicely you have ordered the playlist till now. Thank you again sir.
I have learnt more with you in English although that my English level is not so high than my algorithm teacher in French
I love that after first lessons I can try to solve these by myself and when i succeed it is a big satisfaction!
Thank you so much sir... Your teaching is awesome.
Really liked the way you have clarified all the concepts step wise step.
You are great.
Whoever is editing these videos, has a great sense of humor
Someone hammered my head at 1:00 ! :P
Watching this at midnight, I jumped....
😂😂
Saved me 3 years ago as I was getting my bachelor's in computer science and here u are again sir saving me again as I'm getting a bachelor's in software engineering.
No.1 Algorithms lecturer in the world.
speed @ 1.5 ..😊😄...Perfect
thanks a lot sir for the lectures...
waah ... you are a speedster
There are people who see this for the first time and understand slowly. like me ^_^
3 x pe
100x
Guys, I finally found out why he wrote ( (2^(k+1)) -1 ), instead of (2^k)-1. So, let me make is as simple as possible, because I was also stuck on this very simple doubt for 2 hrs. If we all got a doubt here, it clearly means that we did not count the number of terms. Let's take 2 cases first. See this -> 2^(n-1) + 2^(n-2)+ . . . . . . . . + 2^(2) + 2^(1) + 2^(0). This GP is from 0 to n-1, now, If i tell you to count from 0 to n-1 where n=4, you would totally count 4 digits. That is 0 1 2 3. So there are 4 terms. Just like that for the above equation that I wrote, we have n terms. So, now let's use that general GP formula that we all know about, that is a(r^k -1)/(r-1). You will get 2^n-1 as answer. BUT, BUT, BUT, We all want to know why on earth we all got 2^(k+1) - 1 right. It's really simple. Just like I told you that there are 2 cases. The 1st case was the first equation that I asked you guys to count. Now, I will give you guys another equation as case 2. This equation is the same equation that we will get exactly @10.06 which is 2^n + 2^(n-1) + 2^(n-2) + . . . . . . . . . + 2^0. Now look at this equation really carefully and try to count how many terms there are in this equation. It goes from 0 to n, and not from 0 to n-1(just like in case 1). So let me ask you something, if I asked you to count from 0 to n, instead of n-1, where n=4, you will count 5 terms, that is 0 1 2 3 4. which is n+1 and not n. NOW YOU GOT IT??. in case 2, you can see that there is a an extra term called 2^n. That is the reason we take from 0 to n, instead of 0 to n-1. Instead of just writing this as the next step of the GP equation substitution, he directly wrote it as ( (2^(k+1)) -1 ). That was why we got confused. I really hope this helped everything, as This took about 2 hrs. for me to find and come up with a explanation this detailed.
Thanks 😄
Ookay…
0 to k has k+1 terms. generally if we take 1 to k terms which is k terms, that is why the formula is bit modified
The best channel for advance algorithms and DSA
such crisp and crystal clear lectures. amazing
I am new to your channel, just watched a couple of videos, and am totally hooked. The quality and depth are superb. Subscribing to your channel, and heartful gratitude for putting out such amazing videos. Thank you!
Sir we really need more videos of you, great teacher, love your explanations
Greetings!
Allah pak apko sahat wali lambi zindagi dy or hmesha khush rakhy....❤️
Bestest videos on utube.
Dear Abdul Bari sir, how you keep track of all these information in ur brain? my brain is already rebooting and I am only half way through your playlist. I just want to let you know that this playlist was really helpful. I might not get a good grade in algorithm but I have surely learned better and thank you for that
You explained everything very well and I appreciate your step by step explanation.
Thanks much.
TLDW: Every call has 2 more calls so 2(n-1) = 2(2(n-2)) = 2(2)(2)(n-3), as you can see we are tacking on a 2 each time so 2^n is the worst case
How would the second Test(n-1) be executed?
great explanation, very helpful thank you!
Sir you are God of algorithms for us
T(n)=2T(n/3)+5n
what's the complexity of these equation?
I didn't know, but may be (2/3)power n. I think this is the answer
ig it is O(2^n)
Great Explanation. Thank you for the efforts
Excellent, I was looking for this
Thank you very much. You are a genius.
This explains how binary tree recursion works!! OMG!!
Grande Abdul!
Aap nhi hote to hmara kya hota sir.
Thank you very much.
GREAT GREAT GREAT WORK SIR!!!!!!!!
Just loving your teaching
Need more of courses from your side
Need more teachers like you!!!!!!
Short and comprehensive. Thank you very much for your help!
damn , for the first time in my life I found this easyyy
OMG thank you very much!!!! i finally could understand!!
Hello sir, I was wondering, isn't the sum of a gp series have the formula- Sum= a((r^n)-1)/r-1
I see you used r to the power of n+1? Is it a special case here?
because there are n+1 terms (ik the comment is an year old but it is to help the future students who will study from this video)
Somebody give this man a medal.
Isn't the sum of n terms of a GP = a[(r^n -1)/(r-1)] ? That's what I saw when I searched, and not r^(n+1) -1
Yes
@@SubhamKumar-9009 oh god am also getting confused thank u for analyse it
Interesting to note in all 3 previous videos, the substitution method (counting number of calls) produced a result 1 more than recurrence tree (counting number of prints) method. However in this example of 2T(n-1), these 2 methods both give 2^(n+1)-1. I guess this is because now, the tree method was also counting all the 2^k leaves of T(0), whereas previous videos never counted T(0) in tree method?
absolutely right !!!!
From 8:21 everything is explaining :D
That was awesome. Thank you so much for your help.
On 10:16, is that right?
You are perfect sir.I can understand these lesson.Thanks a lot
Nice 🌺
I love you Abdul!
Perfect👍🏼👍🏼👍🏼👍🏼 thanks, please keep going
Very useful!
Great Sir!!!!
Thank you..
Sir you are truly a legend
How did you simply: 2^(n) + 2^(n) - 1 to 2^(n+1) - 1. At 10:12
its easy just look carefully it will form sum of gp formula
@@Shubham_30_12 could you explain please
2^n + 2^n - 1 = 2*2^n - 1 = 2^(n+1) - 1
2^n + 2^n = 2^(n+1)
Reason:
Let n = 2
2*2 + 2*2
We have 2*2 two times
2*2*2 the last 2 is 1 in (n+1)
We are duplicating the 2*2 to give us 2*2+2*2
Note: the base 2 is important as if it was 3 then we would have triplicate the product of power.
let n = 2
3^n + 3^n
3*2 + 3*2 = 3^(2+1)
(3*3) + (3*3) + (3*3) = 3*3*3
a gold mine in youtube
What happens if I remove "if" condition incase of substitution process ?
loop will go in infinity
How is 1+2+3+...+2^(k-1) = (2^k) - 1?
this is not exactly what is shown in the video ,,actually the obtained series was 1+2+2^2+2^3+2^4+....+2^k and this forms a Gp series ..and sir has clearly shown in the video how to calculate it..
sir you are the best!!
I am having some doubt regarding sum of the geometric mean
5:35 Sum of a GP is a(r^k -1)/r-1 and not a(r^(k+1) -1)/r-1. Where did that k+1 term came from?
It would be really helpfull if someone replies
Look at the number of terms. They're starting from a*r^0 and going upto a*r^k, hence, k+1 terms and a(r^(k+1) -1)/r-1. Had it been starting from a*r^1, it would have been a(r^k-1)/r-1.
@@shubhashish7022 thanks, now understood😌
obrigada cara, salvou demais
Excellent!
In above when 2^n T(0) + 1+2+2²+......+2^n-1
Here when we put the value of n so that T(n) become T(0) so as 2^n should become 2⁰
.
. . 2^n + 2^n -1 = 2⁰ + 2⁰ -1 = 1+1-1= 1
Hence, T(n)= 1
Sir give me some thoughts
Great!!!
Thank You!
Hello Sir, Your teaching is amazing. I need help on Recurrence Relation if T(n) = 3T(n/3) + log n, then what will be the complexity for this relation.
@@abdul_bari thank u sir.. but sir if i have to explain this then how i will write in my paper
@Kenneth Lieu but n have to log n and not its
Sir in the recurrence tree you made I think the tree should be ended with leaf nodes T(n-k) and not T(0) after tracing it for k steps. Though the tree wouldn't be complete if it is further traceable so we will trace it for n steps and hence summation of all those terms will be taken for n steps and which is how we will get the function T(n)=2^(n+1)-1
thanks alot sir !
What is the solution of this recurrence T(n)= (xn)+((1-x)xn)+cn
Thank you for your hard work.
an example of algorithm using this recurrence relation could be tower of hanoi problem
Very nice
omg thank you so much
The formula for GP series goes as Sn = a[(r^n-1)/(r-1)] if r ≠ 1and r > 1
i m confused about the formula you mentioned in the video for GP at time 5.42 in the video.
thank you very much sir !
*Congratulations for 200K+ Subscribers Sir* ..
@@abdul_bari : Welcome Sir..
Sir, I think you got the sum of gp formula wrong, it will be 2^k - 1
this is analysis not the counting
jazakALLAHH
10:16 it must be 2.2^n - 1
Become a Big Fan of you🙏
Thanks sir
why when put into code, T(3) = 7 = 2^3 -1, but not 2^(3-1) - 1 ?
You are great sir.....
Hello sir, in 10.03 you substitute the geometric series formula as (2^k)-1, but in 5.31 when you write the formula isn't it suppose to be ( (2^k)-1/(r-1) ) instead you wrote ( (a(r^(k+1)) -1)/(r-1) ) and so in 4.58 you wrote ( (2^(k+1)) -1 ). May i know why you write k+1 in here instead of k only?
I was quite confused about this too. According to the formula I know for the sum of gp series would be (2^k)-1/2-1. Not quite sure why its different here
Guys, I finally found out why he wrote ( (2^(k+1)) -1 ), instead of (2^k)-1. So, let me make is as simple as possible, because I was also stuck on this very simple doubt for 2 hrs. If we all got a doubt here, it clearly means that we did not count the number of terms. Let's take 2 cases first. See this -> 2^(n-1) + 2^(n-2)+ . . . . . . . . + 2^(2) + 2^(1) + 2^(0). This GP is from 0 to n-1, now, If i tell you to count from 0 to n-1 where n=4, you would totally count 4 digits. That is 0 1 2 3. So there are 4 terms. Just like that for the above equation that I wrote, we have n terms. So, now let's use that general GP formula that we all know about, that is a(r^k -1)/(r-1). You will get 2^n-1 as answer. BUT, BUT, BUT, We all want to know why on earth we all got 2^(k+1) - 1 right. It's really simple. Just like I told you that there are 2 cases. The 1st case was the first equation that I asked you guys to count. Now, I will give you guys another equation as case 2. This equation is the same equation that we will get exactly @10.06 which is 2^n + 2^(n-1) + 2^(n-2) + . . . . . . . . . + 2^0. Now look at this equation really carefully and try to count how many terms there are in this equation. It goes from 0 to n, and not from 0 to n-1(just like in case 1). So let me ask you something, if I asked you to count from 0 to n, instead of n-1, where n=4, you will count 5 terms, that is 0 1 2 3 4. which is n+1 and not n. NOW YOU GOT IT??. in case 2, you can see that there is a an extra term called 2^n. That is the reason we take from 0 to n, instead of 0 to n-1. Instead of just writing this as the next step of the GP equation substitution, he directly wrote it as ( (2^(k+1)) -1 ). That was why we got confused. I really hope this helped everything, as This took about 2 hrs. for me to find and come up with a explanation this detailed.
3𝑇 ( 𝑛-2) + c , can you explain this why its O(3^n/2) more explain pls
Sir i think sum of gp series formula is wrong ... Could you cross check once sir?
good job sir
Why don't we multiply the height of the tree?
thank you, sir, u rly amazing
Great! Thank you
Thank you
the gp series upto 2^k is a(r^k-1)/r-1, so why we taking a(r^(k+1) -1)/r-1
in one previous video you have taken n unit of time for printf but in this you have taken 1 unit of time for printf
love yoou sir
Isn't it n times that print statement inside the if will execute? Why is it counted as 1?
we are not taking the frequency of the statement, instead we are taking the amount of time that is required for that statement to run just one time, that is "1".
Hi, can you provide an answer for T(n-1) + T(n-2) + 1?
I know for a fact that it is O(2^n)
But how do you expand this using iteration method?
Thank you.
@@abdul_bari i don't understand. Why can't it be solved?
Actually Sum of gp is a(r^k-1)/r-1 right?
GOOD JOB
Sir why here we can take time for T(n)=1 instead of T(n)