Prove Recurrence Relation By Master Theorem
ฝัง
- เผยแพร่เมื่อ 22 ก.ย. 2014
- Prove T (n) = O (n^2) using master theorem.
Tutorial:
www.udemy.com/recurrence-rela...
Please subscribe !
►Website: everythingcomputerscience.com/
►Support this channel on Patreon: / randerson112358
►Discrete Mathematics Workbooks:
(1) Practice Problems in Mathematics - www.amazon.com/gp/product/013...
(2)Discrete Mathematics Workbook - www.amazon.com/gp/product/013...
It's a matter of taste, but I prefer to consider the cases without the logarithms. The cases can be rewritten:
Case 1. O(n^d) if a < b^d
Case 2. O(n^d log n) if a = b^d
Case 3. O(n^(log base b of a)) if a > b^d
I have finally understood this topic. Tomorrow is the exam and you have saved the day. Thanks dude!
I had homework on this and had literally no idea the master theorem existed. I can't believe I found this but I'm most certainly glad I did.
Best Master Theorem Explanation I've found. Ty sir. I finally get it.
Thank you!
This was great. Intuitive. Natural. generally awesome.
Thank you so much! I had the hardest time figuring out why each case was divided the way it was but with your table of the d value and its relation to the log was what solved all my questions.
Thanks so much. Applied it, and tried to beat you to the answer. Figured it out, and exclaimed in excitement. Thanks again
I watched almost every vid on the playlist from recurrence relation. I appreciated especially those resolved by iteration method. You are really a good professor and you deserve your subscribers and people saying you're the best, thanks a lot!
Thanks my brother !
@@randerson112358 You're welcome!
Really good explanation, thanks dude.
Really nice and clear. Thank you so much !
Awesome explanation.
Thank you! You saved me a lot of time with this video.
+thomaspagels thank you for watching
This was incredibly helpful and helped clear some things up. Thank you!
Glad it was helpful !
Thanks man! You're kicking my prof's butt at teaching me! And taking about 20 times less time to do it too.
+David Hite thank you !
Thank you! This is really helpful!
Thanks for giving a good example! :)
Thanks a lot man, your video helped me a lot.
Great video. Thank you
Thanks bro, this was really helpful for me :)
Thanks!
Thanks a lot!
thx finally i understand
thanks mr
Perfect video, thank you!
Thank you !
Thanks, saved me from failing my midterm!
Thank you sir!
Thanks for watching!
helpful, thanks!
Thanks Martin !
thanks alot man , you saved my GPA :)
b t haha no problem, I completely understand that statement.
wow :) thankuh so mch ...
How do you solve this if n^d = n^3 log n? What value do you take for d? Thanks!
What if instead of n we have something like nlogn (the equation then being 4T(n/2) + nlogn. does d still remain 1, because in nlogn, n is the highest order term?
The below video should help.
th-cam.com/video/i5kTZof1LRY/w-d-xo.html
Thanks for watching
and
Please subscribe !
randerson112358
quick question:
assume f(n) in the function is some constant; so T(n) = aT(n/b)+f(n), where f(n) is 1, does that mean that since there is no n to derive n^c does that make c = 0?
+Raphael Miller yes exactly! Since n^0=1, c =0
Oh awesome
Hi. Can your explanation of the Master Theorem be found in some book or some online University Couses, or something like that, beside this video? I mean exactly with the usage of n pow d, d instead of f(n), and your 3 cases, with the exact notations that you used? I used your method (which I found great and very easy to understand) for an exam (I am a computer science student) an I might not pass the exam because I did not use the 3 cases of Master Theorem an notations which are presented in most books (probably you know what I mean). And even if the final result was ok, the teacher says he doesn't know this version of the Master Theorem ?! Can you help me so I can have something to back me up? Thanks a million :).
Sure,
This is not my method, the Master Theorem has been used and created/derived by others much smarter than I haha.
Here is a link to a pdf file from a university that uses the same theorem in the video.
cse.unl.edu/~choueiry/S06-235/files/MasterTheorem.pdf
Of course this Master theorem is essentially the same thing as the other master theorem but only for Theta( n^d ).
I am surprised that your professor won't allow you to use this or doesn't understand this seeing as how the rules used here are in the generic master theorem.
Thanks for watching;
randerson112358
I was solving some problems based on this theorem when i came across this one
T(n)= 3T(n/4) + nlogn
In this what do i consider d as?
d=1
However, this Master Theorem is for functions that belong to Theta(n^d) where d > = 0.
Your function nlogn does not.
In this case d > logbase 4 of 3, but again this doesn't matter for this Master Theorem since it's not Theta(n^d).
Try following this video below to determine the answer:
th-cam.com/video/mSX8jFgTCz0/w-d-xo.html
can you solve this for me ?
An array A[1 … n] is said to be k-ordered if
A[i-k] ≤ A[i] ≤ A[i+k]
for each i such that k < i ≤ n-k. For example, the array [1 4 2 6 3 7 5 8] is 2-ordered.
9. In a 2-ordered array of 2n elements, what is the maximum number of positions that an element can be from its position if the array were 1-ordered?
(A) 2n-1 (B) 2 (C) n/2 (D) 1 (E) n
10. In an array of 2n elements that is both 2- and 3-ordered, what is the maximum number of positions that an element can be from its position if the array were 1-ordered?
(A) 2n-1 (B) 2 (C) n/2 (D) 1 (E) n
.... thanks in advance
+Amira Ibrahim
cs.stackexchange.com/questions/25839/k-ordered-array-problem
what about when T(n) = T(2n/3) + 1? d can be regarded as 1 or 0. But 1 > log1 therefore it is Theta(n) but it is really 0 = log1 Theta(1logn)???
+Nerraw please take a closer look, your answer is correct Theta(log n).
D = 0, because n^0 = 1
A= 1, because 1 * T(2n/3) = T(2n/3)
B = 3/2, because n/(3/2) = 2n/3
So yes we use case 2 where 0 = log base (3/2) of 1
to get Theta (n^D * logn) ==> Theta( n^0 *logn) ==> Theta(logn)
Any more questions just leave a comment.
Thanks for commenting, if you find my videos and or comments helpful,
Please subscribe!
randerson112358
+randerson112358 the confusing part is that D could of been mistakenly 0 or 1 since 1^1 and 1^0 =1.
Well, no it could not have been 1 or 0 it had to be 0 because n^0 = 1.
NOTE: n^1 = n
I think I understand your confusion, you see 1 and 1 to the power of anything is always equal to 1.
But the Master Theorem doesn't have 1 in the equation T(n) = a*T(n/b) + n^d
It has a "n" at the end
and so we have to change your equation
T(n) = T(2n/3) + 1 to match.
So by doing this we get the following:
T(n) = 1*T(n/(3/2)) + n^0
NOW:
a = 1,
b=3/2,
d= 0
So you see we are raising n^0 and not 1^0, because n^0 = 1
Thanks;
randerson112358
i guess, b should be > 1 instead of b > 0
+Daniel G. (b > 1) is correct? Not (b > 0)?
+Michael Womack , yes b > 1 and a >= 1.
yes, Michael Womack , randerson112358 - you can read the definition and proof(s) in: Cormen - Introduction to Algorithms.Third Edition. (MIT Press)
Hello Sir. I have a question. Is it true that b > 0? Shouldn't it be b > 1?
E.G:
T(n) = T(n-2)+n
+ebut0oy
Hi, first from your example T (n) = T(n-2)+n you cannot use the master theorem. The recurrence must be in the form as shown in the video
Second b is only restricted to be greater than 0 because you cannot divide by 0. But you can divide by .05 or some number between 0 and 1.
+randerson112358
Thank you very much for the quick answer!
+randerson112358 Actually I've got another problem to solve... This time I don't know how to define "d"...
2^1/2 T(n/2) + log n
How would you solve this? Thank you in advance for your help.
+ebut0oy
The below video should help you
th-cam.com/video/6s_O6uVLSso/w-d-xo.html
+ebut0oy
The below video should help you
th-cam.com/video/6s_O6uVLSso/w-d-xo.html
Why don't you take a nap before making videos?