1.8.1 Asymptotic Notations Big Oh - Omega - Theta #1

hi the next rubric is asymptotic notation and this is a very important topic very important topic in algorithm let us understand what this job it is about so first of all let me tell you that this draw gate is coming from mathematics functions belongs to mathematics so this topic also belongs to mathematics but I for the time complexity we are using functions in algorithms that is the reason this is also used the petitions are also use the notations are used for representing the simple form of a function or showing the class of a function if we have any function we can show that this function belongs to so-and-so class and you already know the composition of functions also which function is smaller and which is greater than which one so we know their order increasing water also now for in presenting any function and simple communicable form so that one can easily get the idea about the algorithm so that's why this is the mostly needed topic forward algorithms because we cannot write a lengthy function every time we need a simple method for representing the time complexity one of the notations used big ball notation this works as an upper bound of a function big Omega notation this works as a lower bound of a function and teton location this works as a average bond of a function average bond of a function any function you can't represent this either upper bound or lower bound or average not know what is useful out of these three this one is useful this one is useful then yd will have these two when you need upper bound if you cannot specify the exact place of any function out of DS then we can show the upper corner 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 one needs and if it is not among DS it may be a multiple of these if it is not even multiple of T's then you may not be able to exactly represent theta then you can go for it before Omega when you will see through these examples to the big old notation as per the definition the definition says that the function f orphan is equals to P Q of G of n if there exists if and only if there exists positive constants C and n 0 such that F of n is less than or equal to C into G of n for all N greater than n 0 or not this is the definition now what does it mean let us understand example if I have a function f of n as equals to 2 and plus 3 then 2 n plus 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 - 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 try to 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 write ten and 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 is 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 him so G of n is what M now therefore they can say F of him what is that if off n 2 and verse 3 yes Big O of M G or furnace and so F of n is Big O of M see I have written death and there so tenon or what I should write so students get confuse 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 second and here was yes so 7 is also true and 10 is also true thousand and also is true anything you write there but make sure that this is greater than that one for some starting value of M now it's off going through all this and stop struggling to get the value there so the simpler Travis you can make this as 2 n plus this is just 3 this also you make it has a 3 end so this will be 2 n plus 3 is less than 5 n and this will be true for all values if I put one there both the site will be 5:5 they are equal if I put any other greater value of n then definitely fine and will be greater so that's it again this is G of N and this is true F of n is Big O of n so simpler try to get this side function as make all these terms as multiples of n for the same function can I write to N squared plus 3n squared and that becomes 2 n plus 3 is less than equal to 5 and square for all values of N greater than equal to 1 yes this is also true is also true then what is G of n here this is CD and this is G of N and as we know that's a safe of n so what is G of n we got and square so can we say that this function the same function can it be can it be big off and square yes this is also true this is not so true whether you say big off and big off n square that's also true as we are writing an upper bound that is bigger that is upper bound so both N and n square becomes the upper bound of that function this F often actually belongs to this class it belongs to the state function this one it means all those functions which are greater than or equal to this one including this this becomes and all these functions including this one on this side becomes global warming and what this exactly becomes this becomes average power average bomb that's it all those functions I can write them as a per bone so saying for this function we go off and is also true we both and square is 4 - f of n is equal to b go off to bar n is also true all those are true but I cannot say F of n is Big O of log n no this is coming on each side this is coming on the world bomb site so I cannot say it is Big O of log n this will be wrong this is wrong and can say all these things all these are true now it is generalizes why do I need to write all those then it is actually equal to this one yes when you write Big O try to write the closest function try to use the closest function so this 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 right so this is about bigger locations Omega R notation as per the definition the function f of n is Omega of G of n if and only if there exists positive constants CN n 0 such that F of n is greater than or equal to C into G of n for all N greater than equal to M 0 just a definition compared to the connotation only the symbol has changed and the symbol has change the inequality sign has changed is was less than equal to mod is greater than 2 that's all the difference now if I take the same example function f of n is equal to 2 and plus 3 then I can write 2 n plus 3 is great just one and so earlier we saw in people we were writing every toe mat and now you can just write one and you can take the help of one here so just one n for all N greater than equal to one right even maybe zero it is starting from zero also so that is not much important anyway you can find out from each value starting you can write down that so 2n plus 3 is greater than equal to 1 n for all n starting from 0 onwards or 1 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 off and this is true so can I see here in stores one can I see login yes this function is greater than not and also so even I can say F of n is omega of log n this is also true that's also true but I can already 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 B Omega of N squared no this is will be wrong because this is becoming an upper bound this is not a lower bomb so I can write anything from this side all will be true anything right that will be true right log of log N or root n log n anything right that is true but which one is useful the nearest one is useful this because this directly belongs to this class so this is equal and the less than one equal agency the function is greater than or equal to this one so this is less than or equal to the function alright so if I write in here the smallest value that maybe two but not useful next one is theta notation as per the definition the function f of n is Theta of G of n if and only if there exists positive constants C 1 C 2 1 and not or n 0 such that C 1 into G of n is less than equal to f of N and that is less than equal to C 2 into G of them if I take the same example F of M is equals to 2 n plus 3 then 2 n plus 3 all the way we found a lower bound that was 1 into n and already we found our bomb that was fighting to n so this is f of n and this is acting as C 1 and this is G of n this is C 2 and this is G of n so both aside we have G of n as M and it is same so then only we can dig it this is G of n that is also G of n therefore I can say F of n is Theta of and 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 as a theta of n square I cannot use this I cannot write any other thing except n because if I write n square here this will be wrong if I write log in here but Logan will be so I cannot use any other thing with the site except this n can be used on good design but a termination is average notation so here I can use only n I cannot use any other rather and this is mostly recommended whenever you have any function and if you are able to represent it annotation that's better but it's not possible and you can go forward people or Omega and one going correcting don't mix this done but best case or worse kiss or forgotten mostly people get confused by mixing this with best case for worst case of algorithm it's not related to best case for worst case mostly people think that big was used for upper bomb sir it is for worst case Omega is for lower bomb so it is for best case no you can use any notation for vestigators any notation for worst case and 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 vs. is not related to case analysis these are just notation for representing bombs of a function

Channel: Abdul Bari

Views: 826,414

Rating: 4.9379597 out of 5

Keywords: Asymptotic Notations, Algorithms

Id: A03oI0znAoc

Length: 15min 46sec (946 seconds)

Published: Thu Jan 18 2018