Recursion Tree Method
Вставка
- Опубліковано 23 вер 2017
- Recursion tree method for solving recurrences running time example
An algorithm analysis example:
What is the running time of the following code ?
Easy Algorithm Analysis Tutorial:
www.udemy.com/algorithm-analy...
►Please Subscribe !
/ @randerson112358
►Videos:
Solve Big O: • Solve Big-O By Definition
Solve Theta: • Prove Big Theta
Solve Big Omega: • Prove Big Omega
►Recurrence Relation Made Easy: www.udemy.com/recurrence-rela...
►Visit my Website:
everythingcomputerscience.com/
►Summation Formulas:
everythingcomputerscience.com/...
polysum.tripod.com/
en.wikipedia.org/wiki/Summation
►Support this channel on Patreon: / randerson112358
►RESOURCES:
web.mst.edu/~ercal/253/SLIDES...
• Recursion tree method ...
• Solved Recurrence Tree...
Helpful Books:
Algorithm Analysis Books:
►www.amazon.com/gp/product/026...
Discrete Mathematics Workbooks:
►(1) Practice Problems In Discrete Mathematics - www.amazon.com/gp/product/013...
►(2)Discrete Mathematics Workbook - www.amazon.com/gp/product/013...
Will you do a proof by induction?
Hi Vitaliy, I have a proof by induction video: ua-cam.com/video/O-8Jn8bkh30/v-deo.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
ua-cam.com/users/edit?o=U&video_id=XWykCejG1Rk
Thank you!
for anyone wondering where the linked video is, ua-cam.com/video/XWykCejG1Rk/v-deo.html
@@username-du2er thank you sm
My left ear liked this
lol
2 hours of lecture just in 15mins. Fantastic!!
Thanks !
Thank you very very much! This is the best of the best lecture! You make hard concept so easy to understand! Thank you!
Suddenly Master Theory doesn't look that bad lol. Great video, really helped!
+Lew_ lol yeah I agree with that.
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 just needed to drop a comment, you are gold man! Thanks for the videos!
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.
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 !!
the way it took me forever to understand this concept until i found this video :,) thank you
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
Thanks for the video! It really helped
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 :)
Thanks a lot, this video was very helpful.
Thanx a lot, the best video of this subject
Thanks for the video. It was very helpful.
You are a beautiful human. My professor explained this in... not an ideal way, and I spent HOURS trying to understand it.I felt very confident as what to do by the 4:52 timestamp.
Thank you Lucas !
Thanks. Helped a lot.
so easy! thanks!
How did you remove the exponent log(n) from the summation?
good stuff man
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 !
Great video man.
bro's goated ong thanks man
Thank you so much! Very helpful and understandable
Thanks for watching !
Great video.Helped a lot!
Glad it could help !
Thank you very much this lecture is magic for me Nice explanation best short tutoriol
Thanks!
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)}
it was great. thank you very much!
Thanks !
Please break down the math simplification step by step
thanks you are the best
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!
Very helpful. Thank you.
Awesome !
can you solve this : T(n)= Sigma i=1 to n-1 ( T(i) + T(n-i) ) +1
Great. Nice voice too, it's very relaxing.
Thank you Louise !
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?
Nice to hear your accent
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
Magician🧙♂
Thank u captain
Great explanation 😀
Thank you !
Make a recursion tree for T(n)=4T(n/2 + 2) + n
Great Video Thanks
Thanks for watching!
how does level 1 looks like if T(n)=4T(..)+..
Thankyou so muchh!
Thank you for watching!
i think it will be O(n2logn) !
good
thank you so much
Thanks for watching!
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.
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
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
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
Thank you
Thanks for watching!
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!
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?
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 am just confused how u got T(1) =4 !silly question bt am confused
I guess its already given in the question !
Your voice is very soothing lol
Haha thanks Amanda!
I love you. I love you so much.
I fuckin love you bro
thamls
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.
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
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 removed the exponent log(n) from the summation?
Thank you
Thanks for the nice comment!