Big Omega Notation - Definition & Example

now let us talk about big Omega notation now big Omega notation is represented by Omega like this and people may not know Omega notation is also corresponding to the best case of an algorithm bigger was corresponding to the worst case and big Omega is corresponding to the best case time complexity of an algorithm so big Omega the idea is very simple if let's consider consider this graph like we have done for Big O the x axis denotes the input Y axis denotes the running time and let's say that for any given algorithm FN is the running time of that algorithm now if we can lower bound this function FN by some by some other function of n then we can say that FN is Omega of G let's say this one move function this is one move function like this this function that let this function be the constant multiple C times GN where GN is also the function of n that means now we are lower bounding this function FN by another function called as C into GN so this curve comes below the function FN the curve C into GN comes below the function FN only after this point so this point is our threshold point this is called as n naught so for all values of N greater than or equals to n not always our FN curve is lower bounded by the curve seen to Jane if we can show this then you can say that FN is Big O of not bigger FN is Omega G n so let's like the definition of definition of Omega notation so it's simple if you can show that FN is greater than equals to C times GN that means this function FN is lower bounded by the function C into GN so here we are talking about something called as lower bound in in Bebo you talk about opera bound in omega you talk about lower bomb so in this case function FN is greater than equals to C into G n where C is a constant C is a constant value and this is this would be true for all values of n that is greater than equals to n not this is only true for the side for values more than and not for this case it does not matter to us if the value of n is very less it does not matter to us we're always trying to find out the how does the algorithm wave for a very large value of n so that value is should be at least at least n naught or more than equals to n now if you can show this that FN is greater than equal to C into G n for some constant C and for all real is n greater than goes to n naught then you can claim that FN is Omega of G and so this is the definition of this is a definition of my big Omega notation now let's try to see let's try to solve some examples on big Omega notation so that we are clear on how it works now let us prove this that is n in e squared plus 3 n plus 3 is equals to R is belongs to Omega of N squared if you want to prove this first you have to recall the definition of Omega which is given here now you want to prove this this one the left hand side is nothing but this is my FN right inside this value is nothing my butt means here now by the definition I have to show that FN should be greater than equal to C into G n now I can write from the second right detain any squared plus 3 n plus 3 should always be greater than any squared is this true if you look at the left hand side the left hand side is 10 times any squared then the right hand side is just any squared so obviously 10 times any squared is more than any squared moreover in the left hand side you have adding 3 n plus 3 also so this this inequality should always be true so is it true for the value N equals 2 n not so in this case first of all I have to demonstrate that this this this is you know represented in the form of f and is equal to C into GN so in this case my value of C is nothing but 1 here I can say that C is equals to 1 you can also choose 10 in E squared you can also sign in a square it's up to you so in that case we'll get a different value of C that's alright now let's continue here the value of C is 1 now I need to find out the value of n not because my definition demands me to find out the value of n not so what's the value of n not here so is this true for all values of n let's let's see since the value of n naught or n is 0 if it's 0 my LHS becomes what it becomes 0 times something is 0 0 this is 3 less this is 3 and we are at this is 0 no this is true right so this is true for n this is true for all values of N greater than equals to 0 so for 0 it's true put 1 it's also true so for all the values more than equals to 0 it's true but remember one thing and not can never be n it can be able to be 0 because M naught is your input input size n is the input size so input cannot be 0 it should at least be 1 so in this case instead of writing into the next to 0 it's always good to write N greater than 0 because n the value of n will never be CEO it should be at least 1 so it's always good to write it's always true for ender than zero so we have now shown the definition we have already shown this we have shown the value of C we have shown this one also so if all of this is being shown here then I can say that 1080 squared plus 3 and plus 3 is equals to Omega of n squared for C being one and n n bigger than zero so this is proved by the definition of definition of big Omega this is how you prove this now let's see you can also prove this you can also prove that you can even do this now this is already proved you can also prove that that means if we make a curve for this it looks something like this so let's try to make a curve for this particular notation so let's make the up curve here something like this so this is my input this is my running time running time all right let's say the function - that is stand in a square plus 3 n plus 3 is represented something like this so let's say this is 10 any squared plus 3 n plus 3 this is a friend now I need to show that I have already shown that this is lower bounded by this is lower bounded by the function N squared this is 1 into n e squared okay now I can also show that this is already proved and this is the plot where a bit this is the value of n naught okay so let me use a different marker now I can also show that then any squared plus 3 n plus 3 is also Omega of 1 a constant value that is I can show that a neigh-neigh square plus 3 n plus 3 by the definition is greater than equals to 1 in this case the function this is my function G and and my C's also 1 here 1 into 1 is 1 ok so C is also 1 this is C and this is my F end so by the definition for value of C equals to 1 and Endor than 0 this is always true right because 1080 squared plus 3 n plus 3 is always better than 1 so this is always true for all values of n greater than equals to 0 but we write it this way because this is how it is demanded by the definition so I can also show that that is by the definition I can see that 10 in a square plus 3 n plus 3 is also Omega of 1 that means I can also lower bound this particular curve by the constant curve that means I can also lower bound this I can lower bound this by one more one more curve let's say the curve is let's say this is the curve for 1 although this is not the curve for 1 but let's say this is the curve ok this is not the exact curve for one okay I'm just giving a demo one is a constant so the curve will come something like this it will be will exactly be something like this something like this ok so you can say you can show it here that you know I can lower bound this by this also by this but here we are looking for the tightest lower bound whenever you're doing Omega we are looking for the tightest lower bound right is meaning the closest one the closer to this is any squared so it's always good to write 10 squared 3n plus 3 is omega n squared is always good to write this but nevertheless this is also true is omega of 1 is also true similarly I can also claim that 10 in a squared plus 3 and plus three is omega n is also true so maybe if this is n ok this is also true this is also lower bounded lower bound in this curve so this is how Omega no recent works

Channel: Sunil Dhimal

Views: 11,303

Rating: 4.8596492 out of 5

Keywords: asymptotic, big omega, best case, algorithm, time complexity, analysis of algorithms

Id: Ut-TsexLA6s

Length: 10min 30sec (630 seconds)

Published: Sun Feb 10 2019