I think what makes Mr. Abdul Bari such a great teacher is the fact that he understands sometimes it is more effective to show someone how to do something rather than merely tell them how to do it. College lectures a lot of the time are way too much telling and not nearly enough showing.
Thank you for your videos! For everyone else who was puzzled by the example at 1:31, here is the analysis: T(n) = T(n/2) + n log 2 (1) => log from 1 base 2 = 0 K = 1 There is no log^p (n) here, so assume p = 0. P = 0 (log^0(n)) (log < k) then it's case 3. This corresponds to option 1 (p >= 0). Therefore the answer is O(n^k log^p (n)). Apply our variable and get O(n^1 * log^0(n)). I saw several people asked the same question and this comment originally was pretty much the same, but finally, I realized that I was wrong :) Thank you again!
I am very much grateful to you sir. Earlier I was very scared to even tap into this subject. I always thought the concepts are too tough. But you made it spectacularly easy. I am currently doing masters but don’t have CS background so I make sure I watch your videos thoroughly before attending my instructor’s lecture. You make these concepts relatively much easier. Thank you so much 😊
Thank you very much. Your explanation turned it easily than I had learned before. It is the power of internet. If i had not found you, my path would be to much hard than it really was.
Super explaining sir, explanation is more than crystal clear Understanding level is 1000% Thank you very much sir I felt much easier after watching these videos
You are the God of Algorithms.Your name should come in Guiness Book of world records for teaching best course on algorithms free of cost.May God Bless you and give you long health.Lots of Love and Best Wishes from Pakistan One suggestion to give you...Kindly add code of algorithms in your videos and explain them and also should discuss what type of questions can come in paper from these algorithms.I am talking about exams in university
I know that my ex will always come here because she is studying algo now. I just wanna say, I miss you and I love you to the moon and back. I really do. Keep it up with your studies ok? ❤
I am struggling to find the complexity of : T(n) = 16T (n/4) + n! Its a frequently asked question on various forums.But lacks a conclusive answer. I will appreciate if you can break it down using Master Theorem
I am little confused in this example. T(n)= 16T (n/4) + n! In order to use master Theorem, we compare it with following form: T(n)=aT(n/b) + theta ( n^k logn^k) So my question changes to : T(n)=16T(n/4)+ theta(n!) However, in last videos, you explained that there is no tighter bound for n!. So we take upper bound and change it to n^n T(n)=16T(n/4)+ theta(n^n) Now. a=16 , b=4 , k=n This implies log a base b= 2 and k=n. Now how do I compare them to arrive at one of the master theorem cases?????
I watched your videos very sincerely and I am able to solve almost all the questions.However this particular question is baffling me. I hope as a teacher you can simplify and explain to students like us.
Thank you sir....I did not analyze the relation between a constant and n Can I say that when the f(n) does not have theta (tighter bound)....we will use its upper bound?? Just like in this case n! did not have tighter bound so instead we used n base n
@@varunchhabra9704 1. 16T(n/4)------> n^2 2. n! ----------------> n! We can't able to compare both Note : For n! We can't able to compare unless we know the value of n Ans: Unpredictable Hope it clarifies ur doubt
@@abdul_bari hello sir. In this particular question the complexity is coming n^1.5. so can we round it off to n^2 and that's why you had written n^2 in the reply ? please clarify. thank you sir in advance :)
Would you be my algorithm analysis professor, please? Pretty please? I'm guessing probably not. Maybe I can send you some cookies instead. 😃 Seriously though, I don't understand my professor at all, and our textbook is of limited value on this subject. You have helped me tremendously. Thank you.
For the last two examples in case 2, there is a non-polynomial difference between n^(logb(a)) and f(n) so Master Theorem does not apply. Not sure how you derived your final answer there.
@@saishadlak6129 I'm not an expert, but I guess we need to ignore + 2 in this particular example and use n^2 to calculate complexity according to the rules defined in the theorem (n^2 will grow every time we increase n, constant will stay the same)
Hi, i dont really understand the first and second example in case 2. you said that the example T(n) = T(n/2) + 1, 1 has the exponent 0 but in the 2nd example -> T(n) = 2T(n/2) + n, n has the exponent 1. can u elaborate cause i am confused
In the 1st example k is 0 and in the 2nd example k is 1 cuz In the 1st example T(n/2) = log 1 with base 2 so its value is 0 In the 2nd example 2T(n/2) = log 2 with base 2 so its value is 1. Then put the formula you will understand clearly😅
Can u please check: for example 3T(n/3) + n^2. so we have „case 3“ and we checke different between f(n) und Omega ^y+є. f(n) = 2 , Omega = 1. but 1+є , for є=0.1. so f(n) = 2 > 1.1 . It’s true what I mean and try to solve ?
@@Manisha-lp3en i agree with your point two, but how can your point 1 say that, log^(8)(100)=8*log(100)? i.e. according to you- log raised to power 8 of 100 is equal to 8 times log 100?
@@Manisha-lp3en my friend can you tell me then with your point of view, what should be the answer of log^(3)(10) with base 10, i.e. cube of (log 10 to the base 10)
Can anyone or sir you yourself help me with the example 2T(n/2) + nlgn as you did it by considering it of case 2 while CLRS stated it to be in the gap between case 2 and case 3 as f(n) is larger but not polynomialy larger.... It would be great help for me I'm stuck.
I think what makes Mr. Abdul Bari such a great teacher is the fact that he understands sometimes it is more effective to show someone how to do something rather than merely tell them how to do it. College lectures a lot of the time are way too much telling and not nearly enough showing.
Thank you for your videos!
For everyone else who was puzzled by the example at 1:31, here is the analysis:
T(n) = T(n/2) + n
log 2 (1) => log from 1 base 2 = 0
K = 1
There is no log^p (n) here, so assume p = 0.
P = 0 (log^0(n))
(log < k) then it's case 3.
This corresponds to option 1 (p >= 0).
Therefore the answer is O(n^k log^p (n)). Apply our variable and get O(n^1 * log^0(n)).
I saw several people asked the same question and this comment originally was pretty much the same, but finally, I realized that I was wrong :)
Thank you again!
thank you
I am very much grateful to you sir. Earlier I was very scared to even tap into this subject. I always thought the concepts are too tough. But you made it spectacularly easy. I am currently doing masters but don’t have CS background so I make sure I watch your videos thoroughly before attending my instructor’s lecture. You make these concepts relatively much easier. Thank you so much 😊
Best ending - "That's all" :D. Very useful video, thank you
Thank you very much.
Your explanation turned it easily than I had learned before.
It is the power of internet.
If i had not found you, my path would be to much hard than it really was.
Best examples I get confused when I try to solve some equation on my own. But worth it thanks sir.
You are a very good teacher. It is 2023 and you are saving my semester. Thank you so much.
Super explaining sir, explanation is more than crystal clear
Understanding level is 1000%
Thank you very much sir
I felt much easier after watching these videos
RESPECT ++10,000
Honestly SIR your style of teaching is Super Awesome.
Thank you very much.
Just by remembering the formulas I can solve them literally in a minutes. JUST WOW
sir never asked to people to subscribe , people who respect his knowledge , and have brain subscribe by theirself
You're my saviour from this course. May God increase you in all ramifications.
Thank you so much Sir.
For making tough subjects easy to learn.
Thanks!
Thank you.. This video give me so much clarity than what my lecture did.
you are a wonderful teacher
i hope i have teacher like you on all my subjects
Thank you very much. You are a genius. 👍👍👌👌🔝🔝🙏🙏
Thank You very much!!! All your videos on DSA are very informative and valuable.
very good explanation all school of computer science student should watch this playlist to strong the concept of design and analysis of algorithm..
Thank you sir for making video on master's theoram ...
in case 3 last example, we should take Big-OH notation right?
Thank You so much sir! Only because of you i am to solve these questions with clarity.
You are the God of Algorithms.Your name should come in Guiness Book of world records for teaching best course on algorithms free of cost.May God Bless you and give you long health.Lots of Love and Best Wishes from Pakistan
One suggestion to give you...Kindly add code of algorithms in your videos and explain them and also should discuss what type of questions can come in paper from these algorithms.I am talking about exams in university
Thank you so much for all your videos!!
I got more respect for you sir. It's 3 am
Sir case 3 me when p
in these cases you can take theta or big O .both are same
Very straightforward, many thanks
sir what are we supposed to do if t(n) = t((n)^(1/2)) is given? How do we tackle the root in the RHS? Thanks!
Thank you so much 💓💓💓💓
Thank you. I can sleep tonight.
I know that my ex will always come here because she is studying algo now. I just wanna say, I miss you and I love you to the moon and back. I really do. Keep it up with your studies ok? ❤
Best explanation
I am struggling to find the complexity of :
T(n) = 16T (n/4) + n!
Its a frequently asked question on various forums.But lacks a conclusive answer.
I will appreciate if you can break it down using Master Theorem
I am little confused in this example.
T(n)= 16T (n/4) + n!
In order to use master Theorem, we compare it with following form:
T(n)=aT(n/b) + theta ( n^k logn^k)
So my question changes to :
T(n)=16T(n/4)+ theta(n!)
However, in last videos, you explained that there is no tighter bound for n!. So we take upper bound and change it to n^n
T(n)=16T(n/4)+ theta(n^n)
Now. a=16 , b=4 , k=n
This implies log a base b= 2 and k=n.
Now how do I compare them to arrive at one of the master theorem cases?????
The question is how do we say that:
2
I watched your videos very sincerely and I am able to solve almost all the questions.However this particular question is baffling me.
I hope as a teacher you can simplify and explain to students like us.
Thank you sir....I did not analyze the relation between a constant and n
Can I say that when the f(n) does not have theta (tighter bound)....we will use its upper bound?? Just like in this case n! did not have tighter bound so instead we used n base n
@@varunchhabra9704
1. 16T(n/4)------> n^2
2. n! ----------------> n!
We can't able to compare both
Note : For n! We can't able to compare unless we know the value of n
Ans: Unpredictable
Hope it clarifies ur doubt
Not all superheroes wear capes.....some wear white shirts
Sir, what would be the time complexity if the question is T(n)=9T(n/3)+n^2/log^2(n)?
O(n^2) / theta(n^2)
t(n)=t(n/4)+t(n/2)+n^2 how to solve these type of equation of complexity analysis?
What is the complexity of this function:-
T(n) = 8T(n/4)+ n^2
Plzz give the answer
@@abdul_bari hello sir.
In this particular question the complexity is coming n^1.5.
so can we round it off to n^2 and that's why you had written n^2 in the reply ?
please clarify.
thank you sir in advance :)
yes sir .
i got it .
thanks for clearing the doubt :)
I guess the answer will be BigO(n^2) because log of 8 with base 4 is less than 2, and according to the case 3, we get n^2.
Input: a = 8, b = 4, k = 2, p = 0
1. log(b)a = 1.xx, k = 2, p = 0
2. This is case 3.1 (1.xx < 2 and 0 >= 0)
3. take the f(n)
Output: n^2
O(n^2) look at -> case 3 episode 2
Thank you for your hard work.
sir in this very first example answer is of order "n" but same problem in previous video have order of "nlogn" how????
please explain.
@om prakash No its the same , please check again
how to solve,
6T(n/3) + n/logn
n^(log(6base3))
Explanation log(6base3) = 1.63 and k=1 so it is case1 and then take n^(log a base b)
Hlo sir.
T(n) = T(n/2) + 2^n
How to solve this relation
Theta(2^n)
Would you be my algorithm analysis professor, please? Pretty please?
I'm guessing probably not. Maybe I can send you some cookies instead. 😃
Seriously though, I don't understand my professor at all, and our textbook is of limited value on this subject. You have helped me tremendously. Thank you.
For the last two examples in case 2, there is a non-polynomial difference between n^(logb(a)) and f(n) so Master Theorem does not apply. Not sure how you derived your final answer there.
kindly explain
In case 3 last question there will be big o or theta
What should we do in Case of
T(n) = 2T(n/2) + n^2 + 2 ??
That extra +2 .. what to do with that
@@saishadlak6129 I'm not an expert, but I guess we need to ignore + 2 in this particular example and use n^2 to calculate complexity according to the rules defined in the theorem (n^2 will grow every time we increase n, constant will stay the same)
n^2+2 €O(n^2)
may I know what about T(n) = T(n/2) + 2^n? Which case does it belong to?
@@abdul_bari Hi sir, I have found logab to be 0, but what is the k and/or p value for 2^n?
i have the same problem
Hi, i dont really understand the first and second example in case 2. you said that the example T(n) = T(n/2) + 1, 1 has the exponent 0 but in the 2nd example -> T(n) = 2T(n/2) + n, n has the exponent 1. can u elaborate cause i am confused
In the 1st example k is 0 and in the 2nd example k is 1 cuz In the 1st example T(n/2) = log 1 with base 2 so its value is 0 In the 2nd example 2T(n/2) = log 2 with base 2 so its value is 1.
Then put the formula you will understand clearly😅
Can u please check: for example
3T(n/3) + n^2.
so we have „case 3“ and we checke different between f(n) und Omega ^y+є.
f(n) = 2 , Omega = 1. but 1+є , for є=0.1. so f(n) = 2 > 1.1 . It’s true what I mean and try to solve ?
What if T(n) = 16T(n/4) + n! ?
In master theorem..
The point is to eliminate the insignificant term. Here n! will clearly dominate. so the ans is O(n!)
Anyone has traced by tree/substitution Case 2: p=-1 or p
Hw to solve T(n) =T(n/4)+T(n/2)+(n*n)
Just WOW!!! Thanks a lot.
case #2 Example Number 6 not sure why (n log n log n) ?
The last two examples of case 2 are not cleared pls explain?????
Please let me know about 7t(n/2) +18n2 and n is a power of 2. Request to take odd numbers and explain don't talk eays powers.
we love you ayre bsa3eed
sir for t(n)=4t(n/3)+n^2 t(1)=1?
Abdul Bari log 4 base 2 is 2
log 4 base 3 is 1.6
Abdul Bari how?
You are so good!
Brilliant
Legend again!
case 3 mee thum big "o(n2)" raknahe sir
Abdul Hoca artık babamdır, üstadımdır.
you are god ,god!!
Sir what is the meaning of log^2(n) ? is it loglogn or (logn)^2 ?
(log n)^2
@@anubhavsharma6263
1. (log^2)n = loglogn
2. (logn)^2 = lognlogn
Both are different
Hence (log^2)n = loglogn
@@Manisha-lp3en i agree with your point two, but how can your point 1 say that,
log^(8)(100)=8*log(100)?
i.e. according to you-
log raised to power 8 of 100 is equal to 8 times log 100?
@@anubhavsharma6263
log^(2n).....Any value in the power of log, we multiply tat value with log........
here ,power=2n, base=2........
Hence (2n)log 1
@@Manisha-lp3en my friend can you tell me then with your point of view, what should be the answer of log^(3)(10) with base 10, i.e. cube of (log 10 to the base 10)
hi thank you so much, how to solve T(n) = 4T(n2
) + 2n
Because we know log b of base a = 2 and k=1, 2>1, we got case 1. Then O(n^(log2))
Log a to the base b is 2*log 2 to the base 2. log 2 to thhe base 2 is 1, so we get log a to the base b as 2. So answer in case 1 is n^2
In this case, a=4, b=2, k=1, then logb(a) = log2(4) = 2 would be > than k=1
So answer is n^(logb(a)) = n^2
Sir I have a question plzz help -
T(n) = T(√n) + n logn ????????
I think It should come to theta(n*logn).
For using masters thm b should be greater than 1 , here it's not
Can anyone or sir you yourself help me with the example 2T(n/2) + nlgn as you did it by considering it of case 2 while CLRS stated it to be in the gap between case 2 and case 3 as f(n) is larger but not polynomialy larger....
It would be great help for me I'm stuck.
SAME
nlog^2n write
thank you sir
Great Video!
Where the sound??
Sir u have taken log2n and log n whole square as the same thing which is mathematically incorrect
how to solve T(n)=T(n/2)+T(n/4)+T(n/8)+n
Thnk u so much sir
Usefull
thank you
he is new god !!
GOD has a face
god
Last two example is horrible.
Thanks!