hi let us look at masters theorem for dividing function so the master theorem we take a recurrence relation in general form so the general form of recurrence relation is P n is equals to a D and by B plus F of N and we assume that it is greater than or equal to 1 means at least it must be 1 and B is greater than 1 and F of and we say that it is of the form theta and power K log n whole to the power of P we assume this the general form now from this we will find out two values Firsters log a base B and the second is ke ke that is power of n see there are different methods here sometimes we take a and B power K first values a and the next values B power K I am taking log a base B and and this will be more easy now based on these two values there are three cases case 1 if log a base B is greater than K then answer is Theta off and bar log a base B so we get the answer in theta otherwise you can take Big O also this is first case k is 2 if log a base B is equals to K these two are same that is log a base B and power of n in function and whatever the power of an in function and both are same equal then again it has three cases if P is greater than minus one means P is not a negative then answer is and poverty and log of P plus one and so whatever the p-value is it is raised for one more time means that whole thing is multiplied by log n I am just writing the condition so that mostly you find these conditions and text book so I am writing the conditions then I will take the examples and I'll show you if P is equal to minus 1 then this is heat of embark a log of log N and if P is less than minus 1 then this is Theta of just n power K we will discard log n so there are these sub cases in case two if these two are equal during the sufferings of cases then case three if log a base B is less than K and this n power K is greater again there are two cases here if P is greater than or equal to zero then answer is Theta off and power K log n power P means as it is same thing and if P is less than zero then it is because and power K just we will take n power K and discard log N that's it now let me take some examples and show you I'll make it more simple for understanding this one through examples so let us solve few examples let us take some recurrence relation that are satisfying case 1 so T n is equals to 2 P n by 2 plus 1 what is a here is 2 what is B here that is true what is F of n this is Kate of 1 what is this theta of 1 T cos 1 is n bar a 0 is there any login no there is no login so for that also I will take log powerlessly to see this one is n bar 0 and a log and power 0 also both are 0 now from this I'll find out log a base B and n power K so what is a K here K is 0 so K is 0 and P is also 0 so what is log in base B log to base 2 is 1 and K is 0 C log amazed me is greater than K this satisfies first condition K is 1 what's that answer I have to write the answer I have to write as theta off and power log a base B log a' base B is what 1 so n power that's it sick example TN is equals to 4 T and by 2 plus and now so directly I will find out these 2 log 4 base 2's what to log a minus B I found out directly instead of finding out a and B and then P I have directly form of this one so what is the K and power is what one what is the P that is zero so this satisfies which case this is two greater than one so it comes under case one so theta of n power log a base B so theta of n power the third example for the same case one T n is equals to a - t TN by 2 + n log eight days - as three and power K is case 1 so 3 is greater heat off and power 3 that's it 8 base 2 is 3 and this is fun only now look at this if the recurrence relation is t + 8 TN by 2 plus n square so k is a 2 there is no P here P is 0 there is no log in here so in simple words you find out this and this and find out log and power of and you see power of n you see so power of n is 2 this is 3 so still this is a great app so on citizen power 3 let me change T M is equals to 9 TN by 3 + 1 what is log 9 B is 3 this is 2 what is the K this is what and power 0 this is n power 0 K is 0 so this is greater this is greater so the answer is Theta of n power this one - if this is n n power 1 power 1 this is greater so again n square only if this is 2 then this is 2 so this is not greater they are equal so they come under case - so as long as this is greater whatever the result you are getting directly put it here let us quickly look at some examples suppose this is so n by 2 and this is n what is this for base to log for ways to 2 and this is 1 so answer will be theta of n square only right if this is eight eight ways to cube this is one so this will be Q if you have ate here and here it is and login so just we see power of n and power K ka you check so this is one this is a base two three so this is greater as long as log a base B is greater than power of n power of n in function f of n we take log base B only alright next we'll look at second case T and is equals to 2 mu T and by 2 plus M log to base 2 is 1 and K is 1 so this is they are equal then what is a P here there is no log n so P is 0 P is 0 right so this is P is greater than minus 1 so what it should be n power K and the log of P plus 1 so whatever in this n log n so P was 0 so I made it as much but in simple terms I'll explain you just watch this don't look at this one right later you can look at you can pause and rewind and you can go through this one so simply I will explain this look at this two ways 2 is 1 and power is 1 so whatever F of n is multiplied by log simple dude of P right this is what we found in the book so unless I show this you may not feel that I am showing mass just here that is the reason I have written it okay it can be minute more simple so was this one now if this is by 2 + n square this is 4 by 2 is what to case how much 2 both are same so what I should do N squared log n this is the answer if suppose already I have log n so again you multiplied by log n so log square n and Square log in so multiplied by n square lock and again it's supposed already this is N squared log n so make it as law the cube so it means when these two are equal log a base me and n power not log and power is same then take this as it is multiplied by log n right take this as it is and multiplied by log n suppose this is log power 5 make it six now right few more see eight log base two and and Q so what is this eight ways to use what three what is in power K and power KK is what three both are equal three three both are equal so the answer is what and power three log in take that and power three whatever F of n is multiplied by log and that's it this is case two in that first one I have shown you now I suppose the recurrence relation is like this 2t n by 2 plus and by log n then all the to bail is to is 1 K power power of n s 1 K is 1 but what is a p-value P is this is in denominator so it is minus 1 then what I should do I told you that if these two are equal they are same this is 1 this is 1 that directly take F of N and multiply well again if I do that the noggin the logon gets canceled no don't do that here the method is little different so take it as he calls and as it is instead of login make it as log of log in and it's done so this what this method says if it is equal to minus 1 so P is minus 1 so this I can write it as into log minus 1 n so this one and even in the same situation if this is denominator is log square n then this will be into log minus 2 n so this will be too small this is were too small - to write then in this case it is less than minus 1 less than minus 1 so in that case don't take this log of log in also don't take log in log of log and also it is power to power 3 something then ignore it just take this one that's all right these are the 3 sub cases in case 2 the third case I will show you TM is equals to T and by 2 plus and square what is a base B log 1 base 2 is 0 and K is a 2 so this is smaller than this one this is greater so this is heat off and square gate off and square right if this is to base to the base 2 is 1 still this is greater answer is n square and if suppose this is having log n then take log in as the keys if you're having loud Square and big log square and a sities whatever it is you take this one power of n is greater than this log M is B so take directly a for fan it is very simple take f of n this is often only power of K is greater than directly take it okay and square log square and that that is already and directly have taken it okay then if this is supposed fullen by 2 and this is a 3 so this is a 2 you see and this is a 3 so the answer is and Q that is greater so whatever it is along with that if you have log also you take it but one thing if that is having log in the denominator but this is greater so don't take the denominator just take n power 3 I said all right these are the cases and I have shown with some examples