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
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.
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!
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?
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
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
+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
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
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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-mSX8jFgTCz0.html
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. ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-i5kTZof1LRY.html Thanks for watching and Please subscribe ! randerson112358
+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 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.
