[Music] in our previous lectures we understood the concepts of big Omega and big Theta notations now we will solve some problems based on big Omega and big Theta notations so let's get started with this lecture and let's see the topics the first topic is Big Omega notation solved problem we will solve the problem based on big Omega notation first and then we will proceed and solve problem based on big Theta notation so there will be a total of two problems that we are going to solve in this lecture let's start with the first topic big Omega notation solved problem here is the problem find the lower Bound for FN which is equal to 10 n² + 5 what is the meaning of lower bound we are interested in finding the lower bound hence we need to understand the meaning of lower bound first we already know what is upper bound upper bound of some function FN is a function which grows asymptotically greater or bigger than FN on the other hand lower Bound for FN is some function which grows asymptotically lesser than FN so we are interested in finding the function which grows ASM totically lesser than FN FN is 10 n s + 5 and we want to find some other function which grows asymptotically lesser than this function how do we find one we already learned how to find the upper Bound for a specific function we need to follow three-step process in order to find the upper Bound for a specific function step number one is to find the dominant term in the given function step number two is to assume some GN based on the dominant term and step number three is to apply the definition of bigon notation in case of finding the upper bound we need to apply the definition of bigon notation in case of lower bound the first two steps are same but the last step is different we need to apply the big Omega definition in case of lower bound so in order to find the lower Bound for FN we need to find the dominant term of FN then we need to assume some GN B based on the dominant term and finally we need to apply the definition of the big Omega notation so now we know what steps we need to follow let's try to solve this problem first we need to find the dominant term in FN here we can observe 10n squ is clearly the dominant term because even for n = 1 this value is greater than this value here we will get 10 and here we have five 10 is greater than 5 so for all n greater than or equal to 1 10 n² is greater than 5 and hence 10n square is the dominant term now let's apply step number two according to step number two we need to assume some function GN based on the dominant term recall we can assume GN by eliminating the constants in the dominant term here we have this constant 10 hence we can eliminate it and we are left with n Square so we can assume that n sare is GN so this is our assumption GN is equal to n² and it might be possible that GN becomes the lower Bound for FN so it might be possible that after applying the definition of big Omega notation GN becomes the lower Bound for FN now let's see whether this is true or not let's apply the definition of of big Omega notation according to the definition of big Omega notation FN is Big Omega of GN if and only if FN is greater than or equal to C * GN for some C greater than 0 and for all values of n where n is greater than or equal to n and c and N are constants according to this definition we can say FN is Big Omega of GN or in other words GN is the lower bound of FN if and only if FN is greater than or equal to C * GN if it is the case that this inequality is true for some C greater than zero and for some n where n is greater than or equal to n then we can say GN is the lower bound of FN now let's find out whether this is true or not let us assume some C let's say C is equal to 10 then after substituting FN by 10 n² + 5 C by 10 and GN by n² we will get this inequality 10 n² + 5 greater than or equal to 10 n² can we say this inequality is true for this C which is equal to 10 and for all n greater than or equal to some n not we can observe that 10 n² + 5 is greater than 10 n² for all values of n greater than or equal to 1 if we plug in 1 here we will get 10 * 1 which is equal to 10 and 10 + 5 is 15 and if we plug in one here we will get 10 10 is less than 15 so for n = 1 this inequality satisfies not only for one for all values of n greater than or equal to 1 this inequality is satisfied therefore we can say this inequality is true for all n greater than or equal to 1 and hence 10 n² + 5 is Big Omega of n² as this inequality is satisfied we can say FN is Big Omega of GN we know FN is 10 n² + 5 and GN is n² therefore 10 n² + 5 is Big Omega of n² for C = 10 and N equal to 1 this is n and this value is 1 that is why I've written n equal to 1 and therefore we can say the GN which we have assumed which is equal to n² is the lower bound of FN which is 10 n² + 5 so we are successful in finding the lower Bound for FN which is n² I hope this problem is clear now let's move to the next problem based on big Theta notation here is the problem show that FN is equal to NQ + 3 n² which is equal to Theta of n Cub we need to show this or in other words we need to prove this that NB + 3 n² is Theta of n cub here we have Theta notation therefore we need to apply the definition of the big Theta notation Theta or big Theta both are one and the same so let's apply the definition of the big Theta notation according to the definition of big Theta notation FN is Big Theta or Theta of GN if and only if C1 * GN is less than or equal to FN and FN is less than or equal to C2 * GN for all values of n where n is greater than or equal to n and C1 C2 and N are all constants we need to prove this inequality is true in order to say that FN is Theta of GN GN is n cub and we already know FN is NQ + 3 n² we now need to prove that C1 * GN is less than or equal to FN and FN is less than or equal to C2 * GN let's first prove that FN is less than or equal to some constant C2 * GN and then we will show that C1 * GN is also less than or equal to FN then we would be able to prove that FN is Theta of GN so let's do this let's prove FN is less than or equal to C2 * GN let us assume some C2 let's say C2 is equal to 2 then we will get NQ + 3 n² less than or equal to 2 * n Cub remember I have assumed GN as n Cub so in place of GN I have written n cub and in place of C 2 I have written 2 so in the right hand side we have 2 * n cub and in the left hand side we have FN which is NQ + 3 n² and I'm assuming the constant 2 here because here we have NQ + 3 n² by making the right hand side 2 N Cub it might be the possibility that after some point 2 N Cub will be greater than or equal to NQ + 3 n² if I have assumed the constant 1 then it will be just n cub and there is no possibility that n Cub will become greater than or equal to n + 3 n² after some point so choose the constant accordingly now getting back to the inequality this inequality is true for n greater than or equal to 3 you can find this on your own for all n greater than or equal to 3 this inequality is true hence we can say FN is less than or equal to C2 * GN we are done with this part we have proved that FN is less than or equal to C2 * GN now let's prove whether C1 * GN is less than or equal to FN or not so this is the second part here I have written FN greater than or equal to C1 * GN this is same as C1 * GN n less than or equal to FN now let's try to show that this inequality is true let us assume some C1 let's say C1 is equal to 1 then we will get this inequality NQ + 3 n² greater than or equal to n Cub here we have assumed the constant 1 and NB + 3 n² is always greater than n Cub therefore this inequality is true for all n greater than or equal to 1 hence we can say FN is greater than or equal to C1 * GN so the second part is also done we have successfully proved that FN is greater than or equal to C1 * GN where C1 is equal to 1 and N is equal to 1 in case of this inequality FN less than or equal to C2 * GN C2 is equal to 2 and N is equal to 3 in case of this inequality FN greater than or equal to C1 * GN C1 and N are both one we know C1 is 1 and C2 is 2 but what about n we need to select n such that both these inequalities must be satisfied we know this INE equality is true for n greater than or equal to 3 and this inequality is true for all n greater than or equal to 1 so we cannot take n as one for both these inequalities because for n = 1 n = 2 this inequality is not satisfied but for all n greater than or equal to 3 both the inequalities are satisfied therefore n must be equal to 3 hence we can say NB + 3 n² which is FN is equal to Theta of n Cub for C1 = 1 C2 = 2 and N not equal to 3 so we have successfully proved that FN is indeed Theta of n Cube so with this we are done with this problem also and this means we are done with this lecture okay friends this is it for now thank you for watching this presentation I will see you in the next one [Applause] [Music]