Solving Recurrences Example - Binary Search (Master Method)
ฝัง
- เผยแพร่เมื่อ 11 ก.พ. 2017
- In this video I solve for the runtime of binary search using the master method.
-------------------------
Follow me on social media!
Instagram | / keithgalli
Twitter | / keithgalli
-------------------------
If you are curious to learn how I make my tutorials, check out this video: • How to Make a High Qua...
⭐ Kite is a free AI-powered coding assistant that will help you code faster and smarter. The Kite plugin integrates with all the top editors and IDEs to give you smart completions and documentation while you’re typing. I've been using Kite for 6 months and I love it! www.kite.com/get-kite/?...
*I use affiliate links on the products that I recommend. I may earn a purchase commission or a referral bonus from the usage of these links.
Thanks a lot . You saved my life 😊
Glad I could help! :)
Instead of constant time only referring to the "amount of time it takes to find m", isn't it actually the amount of time it takes to find m AND the time it takes to compare A[m] against the target value?
Correct
Can you please explain how it fits case 2 of masters theorem and not 1 , I'm confused 😅
case 1 uses big 0. case 2 uses theta. case 3 uses omega. he said it was theta bounded, so case 2. case 2 is the only case that uses theta.
can you please tell me the source of last part.you are saying we need to multiply by logn. your applying case one and then case two.i am confuse,can you please explain more. i tried to read this stackoverflow.com/a/15101630/3222876 and still i am not getting how O(1) become logn.
sunil sarode try looking at case 2 in this link www.google.com/url?sa=t&source=web&rct=j&url=www.cse.unt.edu/~tarau/teaching/cf1/Master%2520theorem.pdf&ved=0ahUKEwiyytbepszUAhVKSCYKHXflBqEQFghEMAM&usg=AFQjCNENMWKaqi_ShyjBJUoUWbCJ3Li1aQ&sig2=3m6SXmZE2p-heV1-LhNupg
the function f(n) and n^log_b(a) is O(1), not the recurrence T(n). As a result of f(n) being asymptotically the same as n^log_b(a)*log^k(n), case 2 applies. In this case k is initially equal to 0 so when we get our T(n) value we need to increase the log term to log^k+1(n)=log^0+1(n) =log(n). Thus our final solution is T(n) = n^log_b(a) * log(n) = 1*log(n) = O(log(n))
sunil sarode I just updated my initial response to be more descriptive. Let me know if everything makes sense now!
hey i got it, it is simply by case two ,cause a=b and thanks lot for you efforts.
Interesting, I have never seen this version of the master method. It still works though.
You set it up correct with:
T(n)=T(n/2)+O(1)
a=1,b=2, k=0,p=0
Because a = b^k (1 = 2^0) this is a case two example.
Our p is greater than -1 so we should select option 2a from the video.
Case 2a states that T(n) = Theta( n^(log_b(a))*log^(p+1)(n) )
Plugging in our values from above we get:
T(n) = Theta (n^(log_2(1))*log^(0+1)(n))
This simplifies to:
T(n) = Theta(n^0*log(n)) = Theta(log(n))
Terrible explanation