Sir thanks a ton for the free help you are giving on TH-cam. Sir the way u have teach, thanks word will we too small for giving in return. Hope sir you will also upload your precious leactures on different subjects of Computer Science.
Professor, first of all, thank you so much for your videos. Now, I have a question, without having to introduce the "m" artifice, can't we just say that, when we reach our base case: T(n^(1/2^k)) = T(2) n^(1/2^k) = 2 n = 2^(2^k) // elevating both sides to ^(2^k) log n = (2^k) log log n = k Thanks again!!!
@all solving using master theorem Take n = 2 power m Then We have t(2 p m) = t(2 p m/2) + 1 Now again let s(m) = t(2pm) Then we can write s(m) = s(m/2) + 1 So case 2 we have Answer as log m But we need in terms of n so we have n = 2 p m thus m = log n base 2 Replace m now Answer log log n Solved using master theorem
@all solving using master theorem Take n = 2 power m Then We have t(2 p m) = t(2 p (m/2)) + 1 Now again let s(m) = t(2pm) Then we can write s(m) = s(m/2) + 1 So case 2 we have Answer as log m But we need in terms of n so we have n = 2 p m thus m = log n base 2 Replace m now Answer log log n Solved using master theorem
@@mostafaom4266 Here is the explanation again actually i forgot () there in power for m/2 read here When you assume n as 2 power m Then expression become T(2pm) = T(2p (m/2)) +1 Now you assume s(d) = t(2pm) If you just put d/2 you will get s(d/2) Then s(d/2) will be t(2p(m/2)) right. Then its solved S(d) = s(d/2) + 1
@@nikhil_somani How assuming s(d) = t(2pm) implied t(2p(m/2)) = s(d/2) ??? It only implies t(2p(m/2)) = s(dp(1/2)). You said just put d/2, so s(d/2) will be equal to t((2pm)/2) not equal to t(2p(m/2)).
It would have been even more great, if he had explained how to apply master theorem of division for root function. As I see, b=√n, a=1, k=0, p=0( after comparing above root function with the master theorem of division) It fell under case-ll with p>-1 So the required time complexity= Θ(log n) for the root function which is different from the actual result(Θ(log log n)).
@@preetikhurana1337 T(n) = T(√n) + 1 Let n = 2ᵐ, then T(n) = T(√n) + 1 becomes T(2ᵐ) = T(2ᵐ/²) + 1 Solving for T(2ᵐ) = T(2ᵐ/²) + 1, Let T(2ᵐ) = S(m) So we have S(m) = S(√m) + 1 We have a = 1, b = 2 and f(n) = θ ( 1 ) = θ ( mᵏ log ᵖ m) where k = 0, p = 0 Using Master's Theorem we have : log a(base b) = log 1 = 0 log a(base b) = k since k = 0, so we have case 2: p = 0, p > -1 (so this is sub case 1) S(m) = θ ( mᵏ log ᵖ ⁺ ¹ m) = θ ( m⁰ log ⁰ ⁺ ¹ m) = θ ( log m) . . . ( i ) since n = 2ᵐ => m = log n( base 2) . . . ( ii ) Substituting ( ii ) in ( i ) we have: S(m) = θ ( log log n ) Since S ( m ) = T(2ᵐ) and n = 2ᵐ therefore we have: T(n) = θ ( log log n ) Is this logically correct? Feels like doing the same problem twice.
@@giantspacemonstr you have done nearly everything Right, just a mistake there... when you assumed, T(2^m) = S(m), then the equation will become -> S(m) = S(m/2) + 1... which leads to a=1 & b=2 and hence log a(base b)=0... As you have written, there would be a=1 & b=1 and hence log a(base b) will not be defined... Since base could not be 1 in a log expression... And that's why also in master's theorem, we have restriction on b as to be strictly greater than 1...
You have to convert the given recurrence relation in such a way that it resembles any recurrence relation of Divide and Conquer Algorithm very closely. Then, you can compare the values of a, b and eventually you'll get the time complexity.
@all solving using master theorem Take n = 2 power m Then We have t(2 p m) = t(2 p m/2) + 1 Now again let s(m) = t(2pm) Then we can write s(m) = s(m/2) + 1 So case 2 we have Answer as log m But we need in terms of n so we have n = 2 p m thus m = log n base 2 Replace m now Answer log log n Solved using master theorem
@all solving using master theorem Take n = 2 power m Then We have t(2 p m) = t(2 p m/2) + 1 Now again let s(m) = t(2pm) Then we can write s(m) = s(m/2) + 1 So case 2 we have Answer as log m But we need in terms of n so we have n = 2 p m thus m = log n base 2 Replace m now Answer log log n Solved using master theorem
Sir a small request on this video atlast you said it can be solved using master theorem of dividing function but I am not able to figure out how to solve this using master theorem of dividing function. I have seen dividing function video but I am unable to apply those formulas here.
Thanks for the lecture sir.. In the problem, why don't we consider n_power_1/2k = 2 Which makes, n= 2²power k could anyone pls solve it or find any wrong in it !!??
if you have assumed n^(1/2^k) = 2 [as, after k steps, T(n) should be 1 i.e., n^(1/2^k)= 2 ] then final result T(n) would be 1 +(1/2)*log(base 2) n instead of 1 +loglog(base 2) n,,,but maybe both the orders are nearly equal
Because sqrt(n) in the time function needs to be an integer. If you didn't make that assumption you could have something like T(sqrt(5)) which is not right.
@all solving using master theorem Take n = 2 power m Then We have t(2 p m) = t(2 p m/2) + 1 Now again let s(m) = t(2pm) Then we can write s(m) = s(m/2) + 1 So case 2 we have Answer as log m But we need in terms of n so we have n = 2 p m thus m = log n base 2 Replace m now Answer log log n Solved using master theorem
n^(1/2)=(n/b) b=3/2 a=1 log a base b =0 k=0 p=0 log a base b = k and p>-1 n^k log^(p+1)n but you get O(logn) and not loglogn. Wondering if someone knows the correct way to do it
@all solving using master theorem Take n = 2 power m Then We have t(2 p m) = t(2 p m/2) + 1 Now again let s(m) = t(2pm) Then we can write s(m) = s(m/2) + 1 So case 2 we have Answer as log m But we need in terms of n so we have n = 2 p m thus m = log n base 2 Replace m now Answer log log n Solved using master theorem
Sir, u said that we can use recurrence relation of dividing to calculate time complexity for root functions, but we haven't consider and power of n in formula of master theorem for dividing. We just a, b, k....??
@all solving using master theorem Take n = 2 power m Then We have t(2 p m) = t(2 p m/2) + 1 Now again let s(m) = t(2pm) Then we can write s(m) = s(m/2) + 1 So case 2 we have Answer as log m But we need in terms of n so we have n = 2 p m thus m = log n base 2 Replace m now Answer log log n Solved using master theorem
sir, how to solve T(n)=2T(n^1/2)+log n... I am following your approach but I am unable to solve it(the log n part which is forming a series)...please explain
Look brother. That's actually n = b^m. In Merge Sort or Binary Search, you divide bigger problems n into either 1 or 2 (in this context, the number of sub problems really doesn't matter) sub problems each of size n/2. So, here b = 2. While solving Divide and Conquer recurrence relations, always assume b to be 2. Now, why n = 2^m? Think about it. The value n in the denominator should be such that it gets fully divided into smaller sub problems (integer division is being discussed here). That is only possible if n is a multiple of b, here 2. Hence, n = 2^k.
Appreciate your time and efforts in enlightening us, can you please help to solve this T(n) = T(n/4) + T(sqrt(n/2)) + n, I'm finding very challenging to solve this.
Sir would you like to help me please, I want to know how can I withdraw my udemy earnings It has been more than a month I'm trying so , my tax docs approved and my Paypal is successfully linked
@all solving using master theorem Take n = 2 power m Then We have t(2 p m) = t(2 p m/2) + 1 Now again let s(m) = t(2pm) Then we can write s(m) = s(m/2) + 1 So case 2 we have Answer as log m But we need in terms of n so we have n = 2 p m thus m = log n base 2 Replace m now Answer log log n Solved using master theorem
@all solving using master theorem Take n = 2 power m Then We have t(2 p m) = t(2 p m/2) + 1 Now again let s(m) = t(2pm) Then we can write s(m) = s(m/2) + 1 So case 2 we have Answer as log m But we need in terms of n so we have n = 2 p m thus m = log n base 2 Replace m now Answer log log n Solved using master theorem
@@kushanksingh3640 @all solving using master theorem Take n = 2 power m Then We have t(2 p m) = t(2 p m/2) + 1 Now again let s(m) = t(2pm) Then we can write s(m) = s(m/2) + 1 So case 2 we have Answer as log m But we need in terms of n so we have n = 2 p m thus m = log n base 2 Replace m now Answer log log n Solved using master theorem
one of the best teacher ever. My professor didn't explain this
Sir thanks a ton for the free help you are giving on TH-cam. Sir the way u have teach, thanks word will we too small for giving in return. Hope sir you will also upload your precious leactures on different subjects of Computer Science.
Professor, first of all, thank you so much for your videos. Now, I have a question, without having to introduce the "m" artifice, can't we just say that, when we reach our base case:
T(n^(1/2^k)) = T(2)
n^(1/2^k) = 2
n = 2^(2^k) // elevating both sides to ^(2^k)
log n = (2^k)
log log n = k
Thanks again!!!
@@abdul_bari Thank you very much for your prompt response. You are very kind.
@@abdul_bari how to use masters theorm that sir has discussed in the previous video to find the relation of root function
how to use masters theorm that sir has discussed in the previous video to find the relation of root function
@@NANDANKUMAR-ps3nw I don't think it is possible to be applied here since b=1 and master theorem restrict that b is strictly greater than 1.
how does finding the value of k lead to the time complexity?
Thank you, Mr. Abdul Bari, for such wonderful explanations ❤❤
Thank you Sir. All the way at UBC in Canada. These profs are nowhere near you Sir.
Thank you so much Sir. You are making algorithms easy to learn. Can you please explain, how can we use Master's theorem in case of root functions?
@all solving using master theorem
Take n = 2 power m
Then
We have t(2 p m) = t(2 p m/2) + 1
Now again let s(m) = t(2pm)
Then we can write s(m) = s(m/2) + 1
So case 2 we have
Answer as log m
But we need in terms of n so we have
n = 2 p m thus m = log n base 2
Replace m now
Answer log log n
Solved using master theorem
@@nikhil_somani This helped a lot!! Thank you
@@nikhil_somani what is the s(m) here?
@@study-me1oe just like variable t(m) we use
@@nikhil_somani how did you get b=2?
one stop solution for algorithm.
Thank you Bari Saab, I will now pass university :) Jazaakamullah ahsanal jazaa
last video of time complexity
😊 Legendary work
Sir, you are different level..... Speechless.....
@all solving using master theorem
Take n = 2 power m
Then
We have t(2 p m) = t(2 p (m/2)) + 1
Now again let s(m) = t(2pm)
Then we can write s(m) = s(m/2) + 1
So case 2 we have
Answer as log m
But we need in terms of n so we have
n = 2 p m thus m = log n base 2
Replace m now
Answer log log n
Solved using master theorem
@@mostafaom4266
Here is the explanation again actually i forgot () there in power for m/2 read here
When you assume n as 2 power m
Then expression become
T(2pm) = T(2p (m/2)) +1
Now you assume s(d) = t(2pm)
If you just put d/2 you will get s(d/2)
Then s(d/2) will be t(2p(m/2)) right.
Then its solved
S(d) = s(d/2) + 1
@@nikhil_somani
How assuming s(d) = t(2pm) implied t(2p(m/2)) = s(d/2) ??? It only implies t(2p(m/2)) = s(dp(1/2)).
You said just put d/2, so s(d/2) will be equal to t((2pm)/2) not equal to t(2p(m/2)).
It would have been even more great, if he had explained how to apply master theorem of division for root function.
As I see, b=√n, a=1, k=0, p=0( after comparing above root function with the master theorem of division)
It fell under case-ll with p>-1
So the required time complexity= Θ(log n) for the root function which is different from the actual result(Θ(log log n)).
we need to take n as 2^m and then solve it T(n)=T(2^m) , by again taking T(2^m) = S(m)
@@preetikhurana1337
T(n) = T(√n) + 1
Let n = 2ᵐ, then T(n) = T(√n) + 1 becomes T(2ᵐ) = T(2ᵐ/²) + 1
Solving for T(2ᵐ) = T(2ᵐ/²) + 1,
Let T(2ᵐ) = S(m)
So we have S(m) = S(√m) + 1
We have a = 1, b = 2 and f(n) = θ ( 1 ) = θ ( mᵏ log ᵖ m) where k = 0, p = 0
Using Master's Theorem we have :
log a(base b) = log 1 = 0 log a(base b) = k since k = 0, so we have case 2:
p = 0, p > -1 (so this is sub case 1)
S(m) = θ ( mᵏ log ᵖ ⁺ ¹ m) = θ ( m⁰ log ⁰ ⁺ ¹ m) = θ ( log m) . . . ( i )
since n = 2ᵐ => m = log n( base 2) . . . ( ii )
Substituting ( ii ) in ( i ) we have:
S(m) = θ ( log log n )
Since S ( m ) = T(2ᵐ) and n = 2ᵐ therefore we have:
T(n) = θ ( log log n )
Is this logically correct? Feels like doing the same problem twice.
@@giantspacemonstr you have done nearly everything Right, just a mistake there...
when you assumed, T(2^m) = S(m), then the equation will become -> S(m) = S(m/2) + 1... which leads to a=1 & b=2 and hence log a(base b)=0...
As you have written, there would be a=1 & b=1 and hence log a(base b) will not be defined... Since base could not be 1 in a log expression... And that's why also in master's theorem, we have restriction on b as to be strictly greater than 1...
@@saa6390 right, I've edited the post. And good insight into why b is strictly greater than 1. Thanks.
Thank you so much, you saved my algorithm hand writing homework.
Respected sir,
How do we apply master's theorem for dividing functions on the root function's recursion relationship to get the time complexity?
You have to convert the given recurrence relation in such a way that it resembles any recurrence relation of Divide and Conquer Algorithm very closely. Then, you can compare the values of a, b and eventually you'll get the time complexity.
@@raunakmitra7868 How can we convert a non-linear function of n i.e root(n) into linear function of n. Can you elaborate?
@all solving using master theorem
Take n = 2 power m
Then
We have t(2 p m) = t(2 p m/2) + 1
Now again let s(m) = t(2pm)
Then we can write s(m) = s(m/2) + 1
So case 2 we have
Answer as log m
But we need in terms of n so we have
n = 2 p m thus m = log n base 2
Replace m now
Answer log log n
Solved using master theorem
@@nikhil_somani genius 👏
@@nikhil_somani Thank you so much for the explanation
thank you so much for deeply explaining the recurrence relations, I am not going to memorize the formulas but derive them according to the code.
Master's Theorem cannot be applied on this question, as b is not greater than 1.
Here, b=sqrt(n).........which is greater than 1. ;-)
Can anyone please explain why why n=2^m and not n = 2 as the boundary condition for the function is n = 2?
Thank you Abdul - all of your videos are priceless! you're a legend. Thank you for helping to improve
Can anyone tell/show me what would be the recursion tree for this relation please? TIA
We cannot apply Master's theorem for dividing function for root functions since, b=1 and condition for Master's theorem is b>1.
more like b= root(n) and not a constant that's why we cannot I guess.
@all solving using master theorem
Take n = 2 power m
Then
We have t(2 p m) = t(2 p m/2) + 1
Now again let s(m) = t(2pm)
Then we can write s(m) = s(m/2) + 1
So case 2 we have
Answer as log m
But we need in terms of n so we have
n = 2 p m thus m = log n base 2
Replace m now
Answer log log n
Solved using master theorem
Why should we assume that n is to be in powers of 2?? 2:25
Sir a small request on this video atlast you said it can be solved using master theorem of dividing function but I am not able to figure out how to solve this using master theorem of dividing function. I have seen dividing function video but I am unable to apply those formulas here.
Sir, You are really great ❤️..Your lectures are outstanding ❤️.. Many many thank you Sir..🙏🙏
How did you calculate the value of 'm' ?
Legendary work!!😊
this is the most simplest solution that you can find!!
Sir I am back again on track. Today I finished this video wonderful explanation.
At the end (minute 5:00) you got the value of K, not N, so, why are you treating K as N?
And, why are you using Thetha instead of Big O?
I have the same question. How is the value of k relating to the theta bound for n
Thanks for the lecture sir..
In the problem, why don't we consider n_power_1/2k = 2
Which makes, n= 2²power k
could anyone pls solve it or find any wrong in it !!??
You can solve with that also
n = 2(²pk)
logn=2pk
loglogn=k
Same answer
Nice catch btw🤘
if you have assumed n^(1/2^k) = 2 [as, after k steps, T(n) should be 1 i.e., n^(1/2^k)= 2 ] then final result T(n) would be 1 +(1/2)*log(base 2) n instead of 1 +loglog(base 2) n,,,but maybe both the orders are nearly equal
sir master theorem can not be applied to this question because b is not greater than 1
This is a huge effort made by you. you explained everything very clearly.
I have one problem for that I am looking solution. please help me with this.
why did you assume _n = 2^m_? I didn't understand that part.
Because sqrt(n) in the time function needs to be an integer. If you didn't make that assumption you could have something like T(sqrt(5)) which is not right.
You rock! All your videos are great!
How to apply master's theorem on this?
@all solving using master theorem
Take n = 2 power m
Then
We have t(2 p m) = t(2 p m/2) + 1
Now again let s(m) = t(2pm)
Then we can write s(m) = s(m/2) + 1
So case 2 we have
Answer as log m
But we need in terms of n so we have
n = 2 p m thus m = log n base 2
Replace m now
Answer log log n
Solved using master theorem
can someone please explain how we can use masters dividing fnc theorem on this root fnc as sir mentioned at the end?
How would you make the recurrence tree for this problem?
Can somebody please explain why are we assuming n is in the powers of 2? (Why we are leting n = 2^m?)
Really appreciate your effort, sir! Thanks a ton!
Sir, how could we directly apply Master's Theorem in this case, I mean what what's gonna be the value of a,b,n and p for that?
n^(1/2)=(n/b)
b=3/2
a=1
log a base b =0
k=0
p=0
log a base b = k and p>-1 n^k log^(p+1)n
but you get O(logn) and not loglogn. Wondering if someone knows the correct way to do it
@@csgeek2321 no not replace by n/b do by n=2powm
Then
T(2powm)=t(2powm/2)+1
Then
S(k)=s(k/2)+1 then solve my master theorem and replace k b
@all solving using master theorem
Take n = 2 power m
Then
We have t(2 p m) = t(2 p m/2) + 1
Now again let s(m) = t(2pm)
Then we can write s(m) = s(m/2) + 1
So case 2 we have
Answer as log m
But we need in terms of n so we have
n = 2 p m thus m = log n base 2
Replace m now
Answer log log n
Solved using master theorem
you are the best man , thank you and keeps on
Sir diving function se kese hoga
log base 1 of 1 is not defineed
Sir, u said that we can use recurrence relation of dividing to calculate time complexity for root functions, but we haven't consider and power of n in formula of master theorem for dividing. We just a, b, k....??
@all solving using master theorem
Take n = 2 power m
Then
We have t(2 p m) = t(2 p m/2) + 1
Now again let s(m) = t(2pm)
Then we can write s(m) = s(m/2) + 1
So case 2 we have
Answer as log m
But we need in terms of n so we have
n = 2 p m thus m = log n base 2
Replace m now
Answer log log n
Solved using master theorem
wow, definitely sublime explanation!
Sir, Thanks a lot. I have a question. Could the result be theta(loglogn)? Does the result have to include 2?
By default log will have base 2 in computer science. So mentioning 2 is optional.
Thank you!
Why is base case n=2? I understand rooting n=1 will be infinite loop. So isn't any n >1 fine to be base case?
Hats off to you Sir !
Just awesome.
Why n = 2^m? Shouldn't it be equal to 2 which is the base case?
sir, how to solve T(n)=2T(n^1/2)+log n... I am following your approach but I am unable to solve it(the log n part which is forming a series)...please explain
facing the same issue. Did u get this?
@@swethabadam6468 i have got this. The answer is coming as O(logn . loglogn)
I became master in Master's theorm
Why n=2^m
For simplicity of solution
Look brother.
That's actually n = b^m. In Merge Sort or Binary Search, you divide bigger problems n into either 1 or 2 (in this context, the number of sub problems really doesn't matter) sub problems each of size n/2. So, here b = 2. While solving Divide and Conquer recurrence relations, always assume b to be 2. Now, why n = 2^m? Think about it. The value n in the denominator should be such that it gets fully divided into smaller sub problems (integer division is being discussed here). That is only possible if n is a multiple of b, here 2. Hence, n = 2^k.
Or we can take n^(1/2^k)=2 to get T(2) in the last equation(terms of k) ...
Appreciate your time and efforts in enlightening us, can you please help to solve this T(n) = T(n/4) + T(sqrt(n/2)) + n, I'm finding very challenging to solve this.
Thank you so much sir, really appreciate your teaching and great videos!!!
Thank you for your efforts
sir please upload videos of recurrence relation with some numerical examples .......
please jaldi upload kijiye
Thank u very much sir
😍😍😍🤗😃
T(n) = T(√n) + n what about this??
It will be n*log(log(n))
But how can we solve using masters theorem?
Plz make a video on soving using Master's Theorem.
But there is a problem b value is less than 1 according to me
Sir would you like to help me please, I want to know how can I withdraw my udemy earnings It has been more than a month I'm trying so , my tax docs approved and my Paypal is successfully linked
Use Payoneer
your are my hero 💕
Where is master's therome for root ???? Did he skip as it's same as that of decreasing ????
@all solving using master theorem
Take n = 2 power m
Then
We have t(2 p m) = t(2 p m/2) + 1
Now again let s(m) = t(2pm)
Then we can write s(m) = s(m/2) + 1
So case 2 we have
Answer as log m
But we need in terms of n so we have
n = 2 p m thus m = log n base 2
Replace m now
Answer log log n
Solved using master theorem
How to solve directly root using Masters theorem
masters theorem can't be applied as b is not greater than 1.
@all solving using master theorem
Take n = 2 power m
Then
We have t(2 p m) = t(2 p m/2) + 1
Now again let s(m) = t(2pm)
Then we can write s(m) = s(m/2) + 1
So case 2 we have
Answer as log m
But we need in terms of n so we have
n = 2 p m thus m = log n base 2
Replace m now
Answer log log n
Solved using master theorem
@@kushanksingh3640 @all solving using master theorem
Take n = 2 power m
Then
We have t(2 p m) = t(2 p m/2) + 1
Now again let s(m) = t(2pm)
Then we can write s(m) = s(m/2) + 1
So case 2 we have
Answer as log m
But we need in terms of n so we have
n = 2 p m thus m = log n base 2
Replace m now
Answer log log n
Solved using master theorem
u will take math class and algorithms in this series
Why n=2^k , please give me the clear reason
you should HAVE explain the MT EXAMPLE............
2^k is always greater than 1 so 2^k is not equal to 1.
thank you so much sir
Thanks a lot
God bless u sir.
Nice video sir
thank you sir!
Thank you sir.
T(n) = 2T(sqrt(n)) + sqrt(n)
Solve this please
My dad always says Indian Muslims are so good. Now I see why!
Why we have assume that T(2^m/2^k)=T(2)????
Thanks🌹
below is the problem, please help me to solve this problem
Thank u sir
Quality!
Thanks
txn sir
Wael's Dad
brovo
Thank You Sir.