hi the next topic is asmic notation and this is a very important topic very important topic in algorithm let us understand what this topic is about so first of all let me tell you that this topic is coming from mathematics functions belongs to mathematics so this topic also belongs to mathematics but as for the time complexity we are using functions in algorithms that is the reason this is also used the notation are also used the notations are used for representing the symbol form of a function or showing the class of a function if we have any function we can show that this function belongs to soo class and we already know the comparision of functions also which function is smaller and which is greater than which one so we know their order increasing order also now for representing any function in simple communicable form so that one can easily get the idea about the algorithm so that's why this is the mostly needed topic for algorithms because we cannot write a lengthy function every time we need a simple method for representing the time complexity what are the notations used Big O notation this works as an upper bound of a function big Omega notation this works as a lower bound of a function and Theta notation this works as a average bound of a function average bond of a function any function you can represent as either upper bound or lower bound or average bound now what is useful out of these three this one is useful this one is useful then why do you have these two why you need upper bound if you cannot specify the exact place of any function out of these then you can show the upper Bond of that function now let me tell you one thing when you find the time complexity of any algorithm the time complexity will be one among these one among these and if it is not among these it may be a multiple of these right if it is not even multiple of these then you may not be able to exactly represent Theta then you can go for big or Omega so anyway we'll see through these examples this is a Big O notation as for the definition the definition says that the function f of n is = to B of G of n if there exist if and only if there exist positive constants C and n0 such that F of n is less than equal to C into G of n for all n greater than n0 or n not this is the definition now what does it mean let us understand example if I have a function f of n is = 2 n + 3 then 2 n + 3 is less than equal to something I should write here such that that is greater than or equal to this one so what I can write I can write anything that should be greater than or equal to this one but one thing I have to take care this function is having two terms so I should not write multiple terms I should write only a single term that single term can have some coefficient that c means it can have some coefficient so what I do is I'll write 10 n is it Greater yes this is greater than this one if I put one here this is going to be 10 if I put one here this going to be 5 so 10 is greater than 5 so this is for all n greater than or equal to 1 onwards right so in this this is f of n this is C and this is G of n so G of n is what n now therefore I can say F of n what is that F of n 2 n + 3 is Big of n g of n is n so F of n is Big of n see I have written 10 n there so 10 n or what I should write so students get confused here then whatever you want you can write there but make sure that this portion is greater than this one or this function is greater than this one so can I write 7 n here also yes so 7 is also true and 10 is also true thousand also is true anything you write there but make sure that this is greater than that one for some starting value of n now instead of going through all this um instead of struggling to get the value there so the simple method is you can make this as 2 N plus this is just three this also you make it as 3 n so this will be 2 n + 3 is less than 5n and this will be true for all values greater than equal to 1 if I put one there both the side will be 5 five they are equal if I put any other greater value of n then definitely 5 n will be greater so that's it again this is G of N and this is true F of n is Big of n so a simple method to get this side function is make all these terms as multiples of n for the same function can I write 2 n² + + 3 n² and that becomes 2 n + 3 is less than = 5 n² for all values of n greater than equal to 1 yes this is also true this is also true then what is g of n here this is C and this is G of N and as we know that's is f of n so what is g of n we got n² so can we say that this function this same function can it be can it be big of n² yes this is also true this is also true whether you say big of n big of n² that's is also true as we are writing an upper bound that is Big O that is upper bound so both n and n Square becomes upper bound of that function this F ofn actually belongs to this class it belongs to this type of function this one it means all those functions which are greater than or equal to this one including this this becomes upper bound and all these functions including this one on this side becomes lower bound and what this exactly becomes this becomes average bound average bound that's it all those functions I can write them as upper bound so saying for this function big of n is also true B of n² is also true F of n is = to Big of 2^ n is also true all those are true but I cannot say F of n is biger of log n no this is coming on which side this is coming on Lower bound side so I cannot say it is big of log and this will be wrong this is wrong I can say all these things all these are true now the question arises why do I need to write all those when it is actually equal to this one yes when you write Big O try to write the closest function try to use a closest function so which is the closest function in this one this is the closest function though if you write any other higher value function also it is true it's not false but it is not useful so we prefer writing anything that is closer to that one right so this is about bigle notations Omega notation as for the definition the function f of n is Omega of G of n if only if there exist positive constants C and n0 such that F of n is greater than oral to C into G of n for all n greater thanal to n0 this the definition compared to big notation only the symbol has changed and the symbol has changed the inequality sign has changed this was less than equal to now it is greater than equal to that's the only difference now if I take the same example function f of n is = 2 n + 3 then I can write 2 n + 3 is greater than equal to just 1 n so earlier we saw in big we were writing every term as n now you can just write 1 n you can take the help of one here so just 1 n for all n greater than equal to 1 right even maybe zero it starting from zero also so that is not much important anyway you can find out from which value is starting you can write on that one so 2 n + 3 is greater than equal to 1 n for all n starting from zero onwards or one onwards so this is f of N and this is C and this is G of n so therefore I can say F of n is Omega of n this is true so can I say here instead of one can I say log n yes this function is greater than log n also so even I can say F of n is Omega of log n this is also true this is also true but I cannot use any value other than this one so if you remember that this belongs to this class so I cannot write anything beyond this one so I cannot say F of n is Big Omega of n Square no this is will be wrong because this is becoming an upper bound this not a lower bound so I can write anything from this side all will be true anything you write that will be true either you write log of log n or root n or log n anything you right that is true but which one is useful the nearest one is useful this one because this directly belongs to this class so this is equal right greater or this is less than or equal I can say right the function is greater than or equal to this one so this is less than or equal to the function all right so if I write any other smaller value that may be true but not useful next one is Theta notation as for the definition the function f of n is Theta of G of n if and only if there exist positive constants C1 C2 and N or n0 such that C1 into G of n is less than equal to F ofn and that is less than equal to C2 into G of n if I take the same example f ofn is = 2 n + 3 then 2 n + 3 all already we found the lower bound that was 1 into n and already we found the upper bound that was 5 into n so this is f ofn and this is acting as C1 and this is G of n this is C2 and this is G of n so both the side we have G of n as n and it is same so then only you can take it this is G of n then that is also G of n therefore I can say F of n is Theta of of n that's it this is the average bound of a function f of N and this shows that this is exactly equal to this one now when I got this one I cannot say F of n is Theta of n² I cannot use this I cannot write any other thing except n because if I write n² here this will be wrong if I write log n here but log n will beong wrong here so I cannot use any other thing both the side except this n can be used on both the side Theta notation is average notation so here I can use only N I cannot use any other value and this is mostly recommended whenever you have any function and if you are able to represent Theta notation that's better if it is not possible then you can go for big or Omega and one more important thing don't mix this one with best case or worst case of algorithm mostly people get confused by mixing this with best case or worst case of algorithm it's not related to best case or worst case mostly people think that bigo is used for upper bound so it is for worst case Omega is for lower bound so it is for best case no you can use any notation for best case any notation for worst case I'll explain this point in some other video when I discuss about best case and worst case analysis so remember that this is not related to best or worst case it's not related to case analysis these are just notation for representing bounds of a function