Hi, the next topic is asymptotic 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 notations are also used. 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 we already know the comparison 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 it. 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 bound of a function. Any function you can represent is 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 bound 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.
And if it is not among these, 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 big O or omega. So anyway we will see through these examples. This is a big O notation.
As for the definition the definition says that the function f of n is equals to big O of g of n if there exist if 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 n0. This is the definition. Now what does it mean? Let us understand. Example, if I have a function f of n is equals to 2n plus 3. Then 2n 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 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 two terms have some coefficient that c means it can have some coefficient.
So what I do is I write 10n. Is it greater? Yes, this is greater than this one. If I put 1 here, this is going to be 10. If I put 1 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 n so g of n is what m now therefore i can say f of n what is that f of n 2n plus 3 is big o of n g of n is n so f of n is Big O 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 in here also yes so 7 is also true and 10 is also true thousand and also 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 instead of struggling to get the value there so the simple method is you can make this as 2n plus this is just 3 this also you make it as 3n so this will be 2n plus 3 is less than 5n and this will be true for all values greater than n than equal to 1. If I put 1 there both the side will be 5 5 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 O of n so a simple method to get this right function is make all these terms as multiples of n for the same function can I write 2n square 3n square and that becomes 2n plus 3 is less than equal to 5n square 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 is f of n. So what is g of n we got? n square. So can we say that this function, this same function, can it be Can it be O?
Yes, this is also true. Whether you say O, O that is also true. As we are writing an upper bound that is O, that is upper bound, so both n and n square becomes upper bound of that function. This f 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 bond average bond That's it. All those functions I can write them as upper bound. So saying for this function, big O of n is also true, big O of n square is also true, f of n is equal to big O of 2 power 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 which side? This is coming on lower bound side. So I cannot say it is big O of log n. 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. 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 right so this is about big O notations Omega notation as per the definition the function f of n is Omega of g of n if and only if there is a exist positive constants c and n0 such that f is greater than or equal to c into g for all n greater than or equal to n0.
This is the definition. Compared to Bigot 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 equal to 2n plus 3, then I can write 2n plus 3 is greater than equal to just 1n. So earlier we saw in Big O we were writing every term as n.
Now you can just write 1n. You can take the help of 1 here. So just 1n. For all n greater than or equal to 1. Even maybe 0. It is starting from 0 also.
So that is not much important. Anyway you can find out from which value it is starting. You can write down that one.
So 2n plus 3 is greater than equal to 1n 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 of n.
This is true. So can I say here instead of 1 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 is 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 write 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. This is less than or equal I can say.
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 any other smaller value that may be true but not useful.
Next one is theta notation. As per the definition the function f of n is theta. of g if and only if there exist positive constants c1, c2 and n0 such that c1 into g is less than equal to f and that is less than equal to c2 into g.
If I take the same example f is equal to 2n plus 3 then 2n plus 3 already we found the lower bound that was 1 into n and already this is equal to 1. found the upper bound that was 5 into n so this is f and this is acting as c1 and this is g this is c2 and this is g so both the sides we have g as n and it is same so then only we can take it this is g then that is also g therefore I can say f is theta of n that's it. 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 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 n here but log n will be wrong here so I cannot use any other thing but the sign except this n can be used on both the sides. 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 O or omega. And one more important thing, don't mix this one with best case or worst case of elliptic. 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 big O 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. This is not related to case analysis.
These are just notation for representing bounds of a function.