Hi Vitaliy, I have a proof by induction video: th-cam.com/video/O-8Jn8bkh30/w-d-xo.html I do not have one specifically for proving recurrence relations, however it is the same technique. Also thanks for watching and that's a good suggestion for another video. randerson112358
Hey! In your solution you never used that T(1)=4 ... After drawing the tree you took the sum from 0 to h. I think it should be from 0 to h-1 and we also add 2^h * T(1) which is the cost of the last level. Therefore the answer is 2n^2 + 2n. Please tell me if you agree or disagree.
Hello, I know this video is very old, and I want to thank-you for teaching me the concept. But, I have a question... Why are you using the summation formula instead of representing the summation as a series of (1/2^i)? Because n^2 can be taken outside as it is a common occurrence throughout the series, then the series can be represented as a constant variable because the series was finite. After applying the Big-O notation rules the constant we had taken will be removed leaving us n^2 and O(n^2). If we were to solve this series we end up with a function where when i = 0 we have f(i) = 1 and when i > 1 we have f(i) = 1 + (1 + 1/2)*1/2^(log(base 2 of n)-1), and the answer is O(n^2) after solving further.
Thanks Shuting Wang, I definitely remember trying to wrap my head around these concepts and not knowing where to start, so I am glad my videos could help you out !
You are literally the best you tuber I have found who teaches these subjects! Keep making videos and helping us learn! Is there any chance you could make a video on guess and check substitution? Not just Iterative substitution?
Could you explain how you get T(1) = 4 ? I thought it would be T(1) = 1. Also, do you split each node into 2 branches because of the 2T? If you had 3T would it be 3 branches from each node?
Isn't the geometric series sum formula S=a(1-r^n)/(1-r). I wasn't sure why in the video you put "r^(n+1)" in the formula. But any way, it doesn't matter, since the theta of n is not gonna be changed by the coefficient~
Hey again, You are correct the geometric series sum formula for Summation from i=0 to n-1 is a(1-r^n)/(1-r) NOTICE here the summation goes to 'n-1', so we get r^(n-1+1) = r^(n) Therefore Summation from i=0 to n is a(1-r^n+1)/(1-r), NOTICE here the summation goes to 'n' instead of 'n-1, so we get r^(n+1) I hope that helps to understand where I got my formula. That was a great question, thanks for watching; randerson112358
I really didn't get the way that you find the upper bound (log2n) in the sum of costs. If you find it from T(1)=4 why did you use 2^i in the same SUM operation?
What you want to do is find how long the recursion takes place. We know the base case is T(1)=4 which terminates the recursion. When does the recursion end? When n=1. When does n=1? Well it ends when n/2^h=1. When you rearrange that you get lg(n)=h. Now what is h? h is the number of levels, right? It indicates how many times the recursion took place. So, if you remember, we find time complexity by summing the cost of every action. The recursion has just went through h times, right? So when we set up the SUM operator, the upper bound is h. But h=lg(n). So we can just put sum_{i=1}^{lg(n)}
how to use recursion tree method when 2 calls are being generated? e.g. T(n) = T(n/4) + T(n/2) + n2 I couldn't figure this out. If you see this message soon, please help me with the solution in a reply comment. Great job btw. Love your videos!
The answer is 2n^2+2n not 2n^2-n. This is because you forgot that T(1) = 4. So the cost is 4n at the last end of the tree. So it becomes [ n^2+ (n^2)/2 + (n^2)/(2^2) + ... + (n^2)/(2^(log n) -1) ] + 4n. Now, you sum the geometric series (excluding the last one 4n) and add 4n. Which is n^2(0.5^(log n) -1) /(0.5 -1) + 4n = 2n^2 + 2n. Nevertheless it is O(n^2).
Hi TheAnalysis2, If I was trying to calculate the recurrence equation solution then yes you would be correct. The recurrence equation is 2n^2 + 2n, and I would've had to consider the base case. But because I was only interested in solving the running time (Asymptotic bound) of the equation, I can ignore the base case since we know it is going to be some constant value. So I would still get the same asymptotic bound no matter what constant value the base case is. I did not forget the base case :) Good observation though ! Thanks for watching ! randerson112358
Can anyone explain to me why n/2^h was set equal to 1 and not 4? In my head, if we "stop" the tree when it reaches all 4s at heigh h, then shouldn't we want n/2^h to be equal to 4 and not 1?
When he goes from level 1 to 2 he puts T(n/4). I know it's obvious but I don't understand the logic there. (n/2)^2 would be (n^2)/4 wouldn't it? My math is too weak for my algorithms course but I gotta tough it out anyways lol.
Binary search allgorithm has a recurrence relation as T(n)=T(n/2) +O(1) T(1)=O(1) I don't know how to initiate using your method as we can't divide O(1) into T(n/2) (thats what i think 😜 correct me please) Anyone????
@@randerson112358 Honestly, I just found a different tutorial. With ADHD, I just can't do that. I've watched a couple of your other videos and they didn't have that many ads. The ones in this video seem to be ill placed.
Excellent question, all I am doing is substituting "n/2" for "n" in the original function. T(n) = 2T(n/2) + n After substituting in the value "n/2" the recurrence looks like the below: T(n/2) = 2T(n/2/2) + n/2 = 2T(n/4) + n/2 Thanks for watching, and please be sure to share this video, and leave likes ! randerson112358
Will you do a proof by induction?
Hi Vitaliy, I have a proof by induction video: th-cam.com/video/O-8Jn8bkh30/w-d-xo.html
I do not have one specifically for proving recurrence relations, however it is the same technique.
Also thanks for watching and that's a good suggestion for another video.
randerson112358
th-cam.com/users/edit?o=U&video_id=XWykCejG1Rk
Thank you!
for anyone wondering where the linked video is, th-cam.com/video/XWykCejG1Rk/w-d-xo.html
@@username-du2er thank you sm
2 hours of lecture just in 15mins. Fantastic!!
Thanks !
My left ear liked this
lol
ayyy its a brotha doing cs lets go. I love when I see another one of us in cs go ahead man do that shit
I appreciate the love !!
big deal
Suddenly Master Theory doesn't look that bad lol. Great video, really helped!
+Lew_ lol yeah I agree with that.
Hey!
In your solution you never used that T(1)=4 ...
After drawing the tree you took the sum from 0 to h.
I think it should be from 0 to h-1 and we also add 2^h * T(1) which is the cost of the last level.
Therefore the answer is 2n^2 + 2n.
Please tell me if you agree or disagree.
I just needed to drop a comment, you are gold man! Thanks for the videos!
Hello,
I know this video is very old, and I want to thank-you for teaching me the concept.
But, I have a question... Why are you using the summation formula instead of representing the summation as a series of (1/2^i)?
Because n^2 can be taken outside as it is a common occurrence throughout the series, then the series can be represented as a constant variable because the series was finite. After applying the Big-O notation rules the constant we had taken will be removed leaving us n^2 and O(n^2).
If we were to solve this series we end up with a function where when i = 0 we have f(i) = 1 and when i > 1 we have f(i) = 1 + (1 + 1/2)*1/2^(log(base 2 of n)-1), and the answer is O(n^2) after solving further.
I wish you could be my professor!!! You have done a much greater job than she does. My brain have never been so clear since this semester started...
Thanks Shuting Wang, I definitely remember trying to wrap my head around these concepts and not knowing where to start, so I am glad my videos could help you out !
You are literally the best you tuber I have found who teaches these subjects! Keep making videos and helping us learn! Is there any chance you could make a video on guess and check substitution? Not just Iterative substitution?
Thanks John !
John Gilmore h
Thank you very much this lecture is magic for me Nice explanation best short tutoriol
Thanks!
Thank you so much for the video! it helped me understand the concept a lot better. Also, you have a very easy to listen to voice :)
Great. Nice voice too, it's very relaxing.
Thank you Louise !
Great explanation 😀
Thank you !
the way it took me forever to understand this concept until i found this video :,) thank you
Thank you very very much! This is the best of the best lecture! You make hard concept so easy to understand! Thank you!
bro's goated ong thanks man
Magician🧙♂
Great video man.
Could you explain how you get T(1) = 4 ? I thought it would be T(1) = 1. Also, do you split each node into 2 branches because of the 2T? If you had 3T would it be 3 branches from each node?
Thank you so much! Very helpful and understandable
Thanks for watching !
Thanks for the video. It was very helpful.
Nice to hear your accent
How did you removed the exponent log(n) from the summation?
thanks you are the best
Please break down the math simplification step by step
so easy! thanks!
Your voice is very soothing lol
Haha thanks Amanda!
Very helpful. Thank you.
Isn't the geometric series sum formula S=a(1-r^n)/(1-r). I wasn't sure why in the video you put "r^(n+1)" in the formula.
But any way, it doesn't matter, since the theta of n is not gonna be changed by the coefficient~
Hey again,
You are correct the geometric series sum formula for
Summation from i=0 to n-1 is a(1-r^n)/(1-r) NOTICE here the summation goes to 'n-1', so we get r^(n-1+1) = r^(n)
Therefore
Summation from i=0 to n is a(1-r^n+1)/(1-r), NOTICE here the summation goes to 'n' instead of 'n-1, so we get r^(n+1)
I hope that helps to understand where I got my formula.
That was a great question, thanks for watching;
randerson112358
Thanks for answering my questions!
good stuff man
Thanks. Helped a lot.
Great video.Helped a lot!
Glad it could help !
Thank u captain
Thanks a lot, this video was very helpful.
I really didn't get the way that you find the upper bound (log2n) in the sum of costs. If you find it from T(1)=4 why did you use 2^i in the same SUM operation?
What you want to do is find how long the recursion takes place. We know the base case is T(1)=4 which terminates the recursion. When does the recursion end? When n=1. When does n=1? Well it ends when n/2^h=1. When you rearrange that you get lg(n)=h. Now what is h? h is the number of levels, right? It indicates how many times the recursion took place. So, if you remember, we find time complexity by summing the cost of every action. The recursion has just went through h times, right? So when we set up the SUM operator, the upper bound is h. But h=lg(n). So we can just put sum_{i=1}^{lg(n)}
Great Video Thanks
Thanks for watching!
Thanks for the video! It really helped
Thanx a lot, the best video of this subject
how to use recursion tree method when 2 calls are being generated?
e.g. T(n) = T(n/4) + T(n/2) + n2
I couldn't figure this out.
If you see this message soon, please help me with the solution in a reply comment.
Great job btw. Love your videos!
it was great. thank you very much!
Thanks !
thank you so much
Thanks for watching!
The answer is 2n^2+2n not 2n^2-n.
This is because you forgot that T(1) = 4. So the cost is 4n at the last end of the tree.
So it becomes [ n^2+ (n^2)/2 + (n^2)/(2^2) + ... + (n^2)/(2^(log n) -1) ] + 4n.
Now, you sum the geometric series (excluding the last one 4n) and add 4n.
Which is n^2(0.5^(log n) -1) /(0.5 -1) + 4n = 2n^2 + 2n.
Nevertheless it is O(n^2).
Hi TheAnalysis2,
If I was trying to calculate the recurrence equation solution then yes you would be correct. The recurrence equation is 2n^2 + 2n, and I would've had to consider the base case.
But because I was only interested in solving the running time (Asymptotic bound) of the equation, I can ignore the base case since we know it is going to be some constant value. So I would still get the same asymptotic bound no matter what constant value the base case is. I did not forget the base case :)
Good observation though !
Thanks for watching !
randerson112358
Thankyou so muchh!
Thank you for watching!
Awesome !
can you solve this : T(n)= Sigma i=1 to n-1 ( T(i) + T(n-i) ) +1
Can you explain how T(1) = 4?
+Michael Muse it's the base case. T (1) could equal 7
Okay, that really helps. I didn't realize that is a value that is provided with the problem. Thanks randerson112358
i think it will be O(n2logn) !
Thank you
Thanks for watching!
Can anyone explain to me why n/2^h was set equal to 1 and not 4?
In my head, if we "stop" the tree when it reaches all 4s at heigh h, then shouldn't we want n/2^h to be equal to 4 and not 1?
Remember T(1) will be equal to 4 , means that when n reaches 1 ,so he do equals it with 1
how does level 1 looks like if T(n)=4T(..)+..
When he goes from level 1 to 2 he puts T(n/4). I know it's obvious but I don't understand the logic there. (n/2)^2 would be (n^2)/4 wouldn't it?
My math is too weak for my algorithms course but I gotta tough it out anyways lol.
I have the same question. Were you able to figure it out?
I love you. I love you so much.
Binary search allgorithm has a recurrence relation as
T(n)=T(n/2) +O(1)
T(1)=O(1)
I don't know how to initiate using your method as we can't divide O(1) into T(n/2) (thats what i think 😜 correct me please)
Anyone????
I'm all for having adds to support you, but I've had an add pop up every 3 minutes. That's horrible for a tutorial video.
Thanks for your opinion ! I do have paid content add free if you would prefer.
@@randerson112358 Honestly, I just found a different tutorial. With ADHD, I just can't do that. I've watched a couple of your other videos and they didn't have that many ads. The ones in this video seem to be ill placed.
good
how are saying that T(n/2)= 2T(n/4)+(n/2)square
Excellent question, all I am doing is substituting "n/2" for "n" in the original function.
T(n) = 2T(n/2) + n
After substituting in the value "n/2" the recurrence looks like the below:
T(n/2) = 2T(n/2/2) + n/2 = 2T(n/4) + n/2
Thanks for watching, and please be sure to share this video, and leave likes !
randerson112358
Make a recursion tree for T(n)=4T(n/2 + 2) + n
how is (1/2)^logn = 1/n ? at12.52 of the video ?
It is a formula of logarithm, a^loga(x)=x, here it is 2^log2(n^-1)=n^-1
I saw a comment that wrote this.
I am just confused how u got T(1) =4 !silly question bt am confused
I guess its already given in the question !
in 12:15 how this happened to thee lg become 1/n
i have exam please. i need to know
rayana saleh
It is a formula of logarithm, a^loga(x)=x, here it is 2^log2(n^-1)=n^-1
thamls
I fuckin love you bro
damn bruh this method is so long
no homo
you lost me by the end
great video! your voice bothers me tho
How did you remove the exponent log(n) from the summation?
Thank you
Thanks for the nice comment!