Prove Recurrence Relation By Master Theorem

Prove T (n) = O (n^2) using master theorem.

Tutorial:

Please subscribe !

►Discrete Mathematics Workbooks:

[kagame]

I have finally understood this topic. Tomorrow is the exam and you have saved the day. Thanks dude!

[crftr-com]

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

[bennettgillig]

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.

[blackfromabove]

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!

[RyanSmith-ntzm]

Best Master Theorem Explanation I've found. Ty sir. I finally get it.

[thedamnbored]

This was great. Intuitive. Natural. generally awesome.

[christopherderrell]

Thanks so much. Applied it, and tried to beat you to the answer. Figured it out, and exclaimed in excitement. Thanks again

[MatthewRiddell]

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.

[DavidHite]

Thanks man! You're kicking my prof's butt at teaching me! And taking about 20 times less time to do it too.

[thomaspagels]

Thank you! You saved me a lot of time with this video.

[andrewortiz]

This was incredibly helpful and helped clear some things up. Thank you!

[christianbouwense]

Thanks, saved me from failing my midterm!

[jaysongrace]

Really good explanation, thanks dude.

[nerzid]

Really nice and clear. Thank you so much !

[SolidCode]

Thanks a lot man, your video helped me a lot.

[MrHylet]

Thanks bro, this was really helpful for me :)

[amiraibrahim]

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

[geminimiller]

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?

[H_Williams]

How do you solve this if n^d = n^3 log n? What value do you take for d? Thanks!

[alexone]

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 :).