DSA Self-Paced Course Preview | Sandeep Jain | GeeksforGeeks

Key Takeaways

hi i am sandeep jain mentor of this dsa self-paced course i am here for complete clarity on the course now the most important question how do we learn dsa for this i offer you my years of experience combined with knowledge in the form of this course now the last question are you ready to invest in yourself before we begin our data structures and algorithm journey let's talk about analysis of algorithms analysis of algorithms is super super important before we start writing algorithms so before we start learning data structures why is it important for a given problem there can be multiple solutions and these multiple solutions might be using different algorithm techniques might be using different data structures how do you decide as a programmer which one is better and this is where analysis of algorithm plays an important role so we are going to discuss this problem where we are given a number n and our task is to find sum of first in natural numbers right for example if n is 3 then our output is going to be 6. how do we get 6 1 plus 2 plus 3 we need to find sum of first 10 natural numbers if n is 5 then our output is going to be 15 1 plus 2 plus 3 plus 4 plus 5. see in this video i have written complete input and output input and output in the upcoming videos to save writing too much text on the board i am going to use ip for input and op for output right just to save this space here so we have an input number n we need to write a function that returns sum of first and natural numbers please pause this video and try to write down a function yourself we are going to discuss three different solutions of this problem and then we are going to compare these three different solutions here are three different solutions written by three different programmers and your solution very likely might be matching one of these three solutions the first programmer has simply returned n into n plus 1 by 2. it simply uses the formula right if n is 3 we are going to return 3 into 4 by 2 which means 6 right the second programmer implemented the loop logic what this programmer did initialize the sum as 0 then 1 by 1 added all the natural numbers first added i equal to 1 then 2 then 3. so this is how you get sum of three natural numbers if n is four then the programmer is going to run the loop for till four and it's going to add one two three four right so this is how the idea of second programmer is the third programmer what it did it used nested loops one loop inside the other and what happens here the programmer runs a loop from one to n right and then runs the loop from j equal to one to y and for every iteration of the inner loop it does some plus plus so what it is doing it is uh having sum is zero then for the one iteration of the outer loop the inner loop will run once only right so it will add one to the sum right so some will be uh getting one added then when the next iteration of the outer loop comes the outer loop ah runs for i equal to two and for i equal to two the inner loop runs two times for j equal to one and j equal to two so sum gets added one two times and in the third iteration one is added three times right we do sum plus plus means we add one to some right so this is how we get again uh sum equal to uh one plus two plus three and we get the result as 6. so this programmer is actually adding 1 n into n plus 1 by 2 times 2 sum and this is how this programmer is getting the sum so these three functions give you the correct output now the question arises which of these three functions is going to take the least time which of these is most efficient see when you talk about time taken by a program it depends upon many factors it depends upon the computer on which you are running suppose you write an inefficient program to solve say this natural number some problem and you run it on a very fast machine then your inefficient program might take less time compared to the other efficient program that you've written and run on a slow machine right the one factor is machine processing power of the machine the other factor is programming language see programming languages like c and c plus plus are compiled languages and java and python are interpreted so what happens in cnc plus plus when you regenerate the binary it's specific to your machine and the binary runs on your machine it's native to your machine but when you write java and python codes the code that is typically generated is intermediate code and it's interpreted it's run line by line by the interpreter that's why the java and python programs typically run slower so it depends upon the programming language also if you have written c and c plus plus it's likely to take less time compared to java and python even if you write these three functions in same programming language and you run on the same system you might not be exactly able to figure out which one is more efficient due to reasons like system load say when you are running an efficient code right the efficient the most efficient of these three at that moment what happened was your system was running a background upgrade it was loaded so what might happen is your system might take more time for an efficient solution now comes one more very very important problem say you and your friend you both wrote different solutions to solve a problem for certain inputs say your friend solution is more efficient and certain other inputs your solution is more efficient now how do you figure out which one is more efficient because for certain inputs his solution is taking less time and for certain inputs your solution is taking less time to overcome all these problems all the problems that i've discussed so far we have a solution called asymptotic analysis which is a theoretical and mathematical analysis with asymptotic analysis we don't even have to implement all the solutions by looking at the algorithms by looking at the solutions we can tell which one is more efficient theoretically let us now talk about asymptotic analysis this is the analysis that we do most of the time whenever we talk about analysis of algorithms we talk about asymptotic analysis only the terms like theta notation big organization that you hear a lot all these terms are related to asymptotic analysis only and they are called asymptotic notations the thing about asymptotic analysis is we measure order of growth of time taken by a function or program in terms of input size for example if input size is n or input value is n does your program grow quadratically linearly is it constant or any polynomial function it has right we check that part only how is how is the time taken growing in terms of input size that's what we measure in asymptotic analysis we'll get a very clear idea when we'll do some examples the thing about asymptotic analysis the best part about asymptotic analysis does not depend upon the programming language does not depend upon the machine and does not depend upon the test cases also we talk about worst case analysis most of the time and that's algorithm is specific not test cases specific one more thing about asymptotic analysis you don't have to implement the algorithms right you have an idea you write this step then you can analyze it is it worth implementing it right you don't have to implement like we implemented three different approaches we could just write the idea of three different approaches or write the algorithm for three different approaches and we could analyze them using asymptotic analysis we did do not have to implement and then measure the time let's now get an idea about asymptotic analysis so what we do in asymptotic analysis is the first thing that we do is we get an expression of time taken by your code in terms of input size so let's understand this with these same examples that we wrote earlier this is our first way of writing the code to find the sum of first and natural numbers we are using a direct formula here so what are we doing in this function is we are doing an addition we are doing a multiplication and then we are doing a division right so if you consider uh these three operations independently you are basically doing three operations and we always assume that a mathematical operation or a comparison operation or any type of operation always takes constant time irrespective of input value whether you uh add 1 million to 1 million or you add 10 to 1 or 5 to 1 they are assumed to be taking the same time in asymptotic analysis right so what we are saying is we are doing our three operations and all these three operations take the constant time irrespective of input value so that is why we have written the time taken as c1 here let's now see the second function in this function uh we are running a loop from 1 to n and then we are doing sum equal to sum plus i so this expression is happening n times right and then there are certain expressions that are happening only once for example this sum equal to 0 is happening once this initialization of i equal to 1 is happening only once this return sum is happening once so there are some things which are being executed constant number of times and some things which are being executed n times so that is why we have written the uh time taken as c2 n plus c3 now one interesting thing is even if it is not exactly n times even if i write this as say less than n or say less than n minus five even in those cases i can write the time taken as c2 n plus c3 why because say uh if i write n minus five times with some c one and then say some c two uh i can rewrite this as with new constants say c six and c seven then i can write this c six uh n plus c seven right now c six is uh same as c1 and c7 is c2 minus 5 c1 right so even if you have a less than sign or you have n by 2 n by 3 it's all can be written as c 2 n plus c 3 if you have n by 2 or n by 3 then your c6 becomes c1 by 2 right so uh as long as you have an expression in terms of n here you can always use c2 and plus c3 for such loops right so this function is going to take this much time let's now see our third example in this example we have this expression which is being executed and into n plus 1 by 2. what are we doing in this logic we are incrementing some these many times so we are ultimately getting the same value here right so if i uh try to compute how many times this expression is being evaluated i get n squared by 2 plus n by 2 right this is what i get so those many times this expression is being evaluated and then there are some other expressions which are being evaluated different number of times for example this is being evaluated once so this is also being evaluated once this is being evaluated n times right because this j equal to one initialization happens for every value of i so overall i can write it as c four n square plus c five n plus c six there are certain things which are happening constant which are taking constant time certain things which are happening quadratic certain things which are happening linear number of times so that's the expression for time taken by this function fund 3 so we got expressions of time taken or for all three functions fun fun one and fun two and fun three see here i have written the time taken for actual implementations i have written the codes which work in c c plus plus and java all the languages but we don't have to implement we can write the algorithm also and analyze the algorithm as well right now our time taken we got in in these forms let's get an idea of order of growth as well so how are these time taken helpful to figure out order of growth see to give you a quick answer uh what are we going to do in the order of growth is we are simply going to take the leading term of every expression we are going to say its constant order of growth does not depend upon n it's linear and it's quadratic right we'll talk about formal definition of order of growth and how how did i say constant linear and quadratic later but a simple rule is you can always uh ignore the lower order terms right and you can say this is what the order of growth is for example here there are three terms i can ignore these two and i can say it's quadratic right that's the simple idea we'll talk about that later let's now get the understanding of order of growth how these expressions help us so let's take some example values let's say you are the one who wrote this efficient code and your friend wrote this inefficient code right and you ran it on a machine where the value of c1 is 13 right you run it on a slow machine where it takes 13 units of time to do this works this constant amount of work or even the c1 is 13 for your machine right now your friend ran it on a different machine which is slightly faster and for him say c2 is uh 2 and c3 is 5 right so your friend got the expression 2 n plus 5 for time taken and you have the expression as 13 right so what happens uh with these two machines and these two functions when you run them and i'm assuming that every time you run them they are going to have the same constants the machine load does not change right so what happens uh in in time taken is your machine's time is always going to be 13 right it's constant value fun one your function it's always going to take 13 units of time on your machine your friend's time taken depends upon n so it's going to be uh taking for n equal to 1 it's going to take uh it's going to take 7 for n equal to 0 it's going to take 5 for n equal to 3 uh you can put the value and you can get and if i find the intersection point of these two functions i can get the intersection point as 4 right 13 equal to 2n plus 5 and i get the n as 4 right so this is what the value of this intersection point is now if you take a look at this this intersection point what happens is after this intersection point your friends function is always going to take the more time right even if your friend chose a faster machine had a faster machine than you and you had written uh your code fast but your machine was slower but after value of four your friends uh code is always going to take more time than you that's the beauty of order of growth because the order of growth of this function is higher and this function is lower it's constant and it's linear right the machine specific things go away right after the value of four now uh even if you choose a further slower machine say you have uh n equal to thousand and your friend has uh even lower values even in those cases there would be a value of n after which this expression because this is growing with n identity is constant so there will be a value of n after which this expression will have more value than your value here i have redrawn the graph for different constant values see this time you got even a slower machine you had to run your logic your fun one function that you wrote on a mobile phone and your friend got even a faster machine so the constants for you are 1000 and constant for your friends are say one and one so the value of the function fund to the time taken for fund two is n plus one because the friend is running on even a faster machine and for you it's only uh it's high value it's thousand right you've got a mobile phone now now your friend says that my program see my program is taking less time now how do you prove that your program is faster so the asymptotic analysis works here as well what is going to happen is uh there is going to be a value of n after which your friends program is always going to take uh more time it's just that the value of n is higher this time because you have a slower machine your friend has a faster machine so if i compare these two functions n plus one and thousand and if i say give me the values uh for n for which i have higher value of this expression i get the value of n as triple nine after triple line and triple line is this point after this value the fun one is always going to take more time than fun too right the fun one is always going to take more time you can put the values it's going to be a thousand a thousand one thousand true and thousand three and so on so that's what uh the great thing about asymptotic analysis and asymptotic notations are we are going to see mathematically also why it is true that if something is having higher order of growth then that thing always have higher value after certain value of n we'll discuss that how is it mathematically true before we end this video let's quickly talk about fund 3 also fund 3 is a quadratic function right and quadratic functions grow even faster so quadratic functions grow like this right so fund 3 is going to have a value again after which it's going to take more time than even fun one and fun two before we end this video let's quickly talk about fun three also fun three is a quadratic function so it's going to have a graph like this right a quadratic growing graph and you can notice that after a certain point fun three is having more time than fun one and if i compare it with fun2 then the way i've chosen the constants here drawn the graph here it's having higher value than fun2 all the time right one last thing about asymptotic analysis and this graph we are always going to be considering this quadrant of the 2d coordinate system because the time taken by an algorithm cannot be negative right it is either zero or growing with the value of n and n is typically size of input right and this value of size is always going to be zero or greater than zero so whenever we draw the graph or whenever we talk about asymptotic functions asymptotic analysis see these are the functions of time taken right there they show you how much time taken by fund two and how much time taken by fund one right so they are always going to have a value greater than or equal to 0 same is the value same as the case for input size n so the basic idea of analysis of algorithm the main idea is to measure order of growth of time taken by algorithms that's the main main idea that we use however this has some limitations if you remember the previous example when we were comparing thousands with n plus one see an algorithm takes thousand instructions or thousand unit of time and there is an another algorithm that takes n plus one unit of time this thousand may be higher because this is probably implemented in a programming language that takes more time and maybe on a it's running on a machine which is slower but it takes thousand units of time and we saw that when n becomes greater than triple nine then only this algorithm starts taking less time compared to this algorithm now imagine an environment where your n never reaches more than triple line when you were comparing your program which was constant with your friends program suppose it never happens that input size goes beyond triple line right so that's a limitation of this order of growth analysis you know we always talk about limit n tends to infinity we always talk about that right however in practically it might never reach that limit right it might never reach that high value triple nine but that's what we talk about we talk about only large input size in this theoretical analysis that's what everybody does when we analyze algorithms theoretically let us now talk about order of growth order of growth is the main main criteria when we do theoretical analysis of algorithms the idea is simple if order of growth of the function which represents time taken by an algorithm is more compared to another algorithm then we say that this algorithm is a bad algorithm so fn is said to be having higher order of growth than gn if limit n tends to infinite f and divided by g n becomes infinite and higher order of growth means we say the algorithm whose time is represented by fn is a bad algorithm right so if fn represents a bad algorithm then fn by gn for n tends to infinite would be infinite or g n by f n for n tends to infinite is going to be 0. so i'm going to use this expression here this expression to prove that order of growth of fn is higher i've taken this example n square plus n plus 5 and 2 n plus 5 and i'm going to use this expression to show that fn is growing faster and please remember all this discussion is under these assumptions first quadrant right of 2d coordinate system where n is 0 n is greater than equal to 0 and f n and g n are also greater than equal to 0. they are mainly positive functions so let's compute the value of this expression fn divided by our gn divided by fn when n tends to infinite so we have 2n plus 5 divided by n square plus n plus 6 and we are talking about limit n tends to infinite so when we talk about order of growth we always talk about n tends to infinite although it might not be a practical idea as we saw in the previous video when we were talking about fun one and fun two and we saw that fun one was having less value only when n was greater than triple nine right and in practical situation it might happen that your input never reaches more than this value right but that is fine because it's theoretical analysis and that's what we do here right so let's talk about uh this expression value the simple idea to compare order of growth of two functions and get the value of this take the highest order term and divide it by both numerator and denominator denominator highest growing term highest growing term is n square so we divide both numerator and denominator by n square and what do we get 2 divided by n plus 5 divided by n square divided by 1 plus 1 by n plus 6 by n square now when n tends to infinite what this value is going to be when you have n in denominator all those terms are going to be 0 when n tends to infinite right so this is going to be 0 this is going to be 0 and this is going to be 1 plus 0 plus 0. so what is this value this value is 0 right 0 divided by 1 is equal to 0. so you get the value 0 you get the value of this expression gn by fn is 0 and this is the required condition to prove that fn is growing faster than gn right so order of growth of fn is faster than gn so if fn represents time complexity of an algorithm and gn also represents time complexity of algorithm another algorithm then we say gn is a better algorithm there is a direct way to compare order of growth of two functions in fact there is a direct way to find out order of growth of any function under the conditions when n tends to infinite and we are talking about first quadrant and greater than equal to zero and that function is also positive under these conditions we can quickly find out order of growth of any function and we can quickly compare these order of growth the idea is simple given a function we ignore the lower order terms we ignore the leading constants now how do we decide which terms are lower order terms we must kind of remember this thing that constant is the lowest growing thing it never actually grows it remains constant log log n grows faster than constant then log n then n is the power 1 by 3 in half then n n square n cube n 4 2 raised to the power n n is 2 over n these are the commonly seen terms in algorithms now we talked about ignoring lower order constants ignoring leading constants and then how do we decide which one is lower let's do some examples say i have a function f1 whose value is 2n square plus n plus 6 and i have another function gn whose value is 100 n plus 3. now how do you decide which one is better or which one is faster growing you ignore the lower order terms of both the functions so from here you can refer n square is higher order term so you can ignore n here right you can ignore six here and you can ignore the leading constant you can ignore this constant too so you say that athens order of growth is n square and what about g n you can ignore the lower order term which is a constant you can ignore leading constant and you can say g in order of growth is linear and now if there are two algorithms and they have these times taken by them then you definitely say that gn is better because n is less than n square the time taken by g n is going to grow slow when n grows and we are talking about n tends to infinite so that's the general idea the direct way to find out the order of growth ignore the lower order terms ignore the leading constants and find out the order of growth and simply compare them and how do you decide which chunks are lower order you can use this and the same thing you use to decide which is having better order of growth in these finally found order of growth let us do some exercise to find out order of growths of functions and compare them say you have fn as c1 log n plus c2 and gn as c3n plus c4 log log n plus c5 this c1 c2 c3 c4 c5 they are machine specific constants right so they are doing some addition subtraction in your algorithm and we just put the constants in place of them now which one is growing faster please pause this video find out the order of growth about the functions then compare them so you can ignore the lower order terms in here c2 can be ignored leading constant can be ignored so you get the order of growth as log n which one is lower order term here this one because this comes before n so you can ignore it you can ignore it and you can ignore the leading constant so the order of growth of this function is n now which algorithm is better this algorithm was this algorithm so this algorithm is definitely better because its order of growth is less it grows logarithmically let us do one more exercise c 1 n square plus c 3 plus c 4 c 5 n log n plus c 6 plus c7 what is the order of growth of this function we ignore the lower order terms ignore the leading constant we get n square what is the order of growth of this function ignore the lower order terms ignore the leading constant and log n now which one is faster or which one is having less order of growth see we can simply cancel one n with the other end and we get here n extra and here we get log n extra so n is definitely more from this and this so we say this algorithm is faster right it's going to take it's going to grow slow and we can say order of growth of this algorithm is more right so this algorithm should be preferred in when you have two algorithms with these times let's now talk about average worst and best cases of algorithms before we talk about that let's take a closer look at this example function what are we doing in this function we have written a function that takes an array as input size of array has another input initializes the sum of array elements as 0 then traverses through array elements and computes the sum right so this function is basically doing the array element sum and returning the sum please pause this video and try to guess the order of growth of this function the time taken by this function is clearly c1 n plus t2 there are certain things that we are doing constant number of times like this initialization this initialization and returning sum at the end and then there are certain things that we are doing linear number of times like this statement is being executed in amount of times this condition is being checked linear number of times this increment is happening linear number of times so we have c 1 n plus c 2 right and order of growth can be easily seen as n now please see this example too and try to guess the order of growth of it see due to some business reason what we have here is if the user provides even size array we return the sum as zero otherwise if the user provides or size array then we do the actual rsm and return the sum at the end right now if i ask you about order of growth you can't make a general statement you can't say that the order of growth is constant or linear because it depends upon the type of input if user input is even sized then it's going to take the constant time if the user input is or size then it's going to take the linear time so what we do in algorithms is we divide all cases into three cases for algorithms and those three cases are best case average case and worst case now what is best case you must have guessed it what is the minimum order of growth of an algorithm for example in this algorithm the best case happens when user provides an even sized array and in this case our time taken or order of growth of this algorithm is constant right so the best case uh complexity or the best case thing for this algorithm is constant now what is average case see average case goes like this it's like time taken for every input say uh you know that you've written this function and users of this function are going to provide these thousand different inputs you compute the order of growth or time taken for every input right those thousand inputs and then divide the sum by thousand like it's just like doing the normal average thing so uh many times we don't know what thousand inputs users are going to provide so we make some assumptions and what assumption i have made here is i have made this assumption that a user is going to provide half of the time even input and half of the time odd input i've written that under the assumption that even and odd are equally likely so what is going to happen here it's going to be linear in half of the cases when the user provides odd sized input array and it's going to be constant in rest half of the cases when user provides even size input array and if i uh do the sum of these two and divide it by 2 right i am going to get something like c1n by 2 plus c 2 divided by 2 plus c 3 divided by 2. so c 1 c 2 c 3 are some constants we can ignore them these are lower order terms we can ignore the constants of the leading terminal as well so we get n again so the order of growth in average case is linear but average cases something which requires you to make certain assumptions about the input or an ideal situation requires you to know the exact input then compute the average that's why average case is not typically done although we would like to know uh what is the time taken in the average case but we can't do it many times because we don't know how user is going to use this particular function what is going to be the distribution what are going to the out inputs we don't know those things talking about the best case see best case is also not used if you are building a software and if you tell your user in the best case uh my software is going to respond in 0.001 microsecond but i don't know about the worst case or average case it might take hours nobody is going to buy your software right so we do not provide much information when we mention the best case of an algorithm right worst case is something that we use most of the time we find out what is the input case for which it's going to take the maximum time or it has it is going to have maximum order of growth and here it is clear that if user provides or sized array then it's going to take the maximum time or it's going to have the maximum order of growth and that order of growth is linear right so the worst case of this algorithm is linear to summarize the worst case average case and best cases see many times when you write program if your program does not have any condition that it's going to have different orders of growth of different cases you can simply say one line of the order about the order of growth and you can say that's what the order of growth is for example uh the example one where we were doing the simple sum of the array elements other real world example can be uh for example you want to find out the maximum in an array in that case you will have to traverse the area to find the maximum right there is no best case no worst case no average case right it's like always going to be linear and similarly minimum in an array right it's always going to be linear but many algorithms they have different cases in for certain input they take different time and for certain other input they take different other times and there are many standard algorithms also like this there is insertion sort algorithm if you provide sorted input it takes linear time if you provide a reverse order input it takes quadratic time so the cases when your algorithm has different times for different types of inputs in those cases we divide the cases into three cases best average and worst best is something which is bogus we don't require the best case saying that its minimum time is this is of no use average is something we would like to know but impractical many times and worst case time complexity analysis worst case asymptotic analysis is something that we do most of the time we find out what are the case what are the input types when this algorithm is going to have maximum order of both we use that order of growth most of the time to indicate it as time complexity of the algorithm let's now talk about asymptotic notations asymptotic notations are the mathematical notations to represent order of growth of any mathematical function there are mainly three popular asymptotic notations big o which represents exact or upper bound on order of growth then theta which represents exact order of growth then omega that represents exact or lower count so why do we need exact or upper why do we need exact or lower say if i have a function c 1 n plus c 2 i can ignore the lower order terms right i can ignore the constant i can say that order of growth is n right and if i take another example say if i have c 1 n square plus c2 log n plus c3 right i can always tell you the uh exact order of growth i can ignore the lower order term i can ignore the lower term i know the constant i can say order of growth is n square right so i can always uh use theta rotation or i can always tell the exact order of growth why do we need a bigger notation which is exact or upper or omega notation which is exact or lower let's understand it with an example say uh this is a linear search code and this example is similar to the examples that we discussed in the previous video where we talked about in certain cases we were taking constant time in certain cases we were having linear time when we talked about that get some function modified that gets some function so the same thing happens here if you talk about linear search and say if you have this array and say if you are searching for an element x write this function what it does it takes an array size of the array and an element to be searched in the array traverses through the array as soon as it finds a match it returns the index of that match and if it does not find any match after traversing the whole error it returns -1 so say you are searching for 10 only so what will happen this case it will find the 10 at the first place it will return immediately so it's taking only constant time when the element is present at the first location and when the element is not present at all that's going to traverse through the whole array right it's going to come out of the loop it's going to return minus 1 for example if you search something like 75 right it's going to traverse till this point and then it's going to realize element is not present it's going to written -1 so in the worst case it's going to do linear time now if i want to uh say anything about order of growth of this function i have to say something like this say in the best case it takes a constant time in the worst case it takes linear time and if i just want to say this thing in one line or say i don't want to evaluate the best case right evaluate other cases i just evaluate the worst case and what i say is i say this algorithm takes big o of n time right big o of n means uh it's either linear or less than linear as i said it represents exact or upper bound so if you have a function which is c 1 n plus c 2 you can write it as big o of n mathematically you can write it as big o of n square also right because any upper uh order of growth can also be written in bigger notation right you can write anything higher than n right not less than n you can write either n in bigger rotation or you can write anything higher than it you can write n log n n cube and 4 or anything so the point is if i say that this algorithm is big o of n what it means is it means either it takes linear time or takes less than linear time so with bigger notation i can talk about this time taken of this algorithm in one line we will be discussing uh bigger notation theta notation omega notations in separate videos in detail the idea here is to introduce these three notations pago means exact or upper for this algorithm i can say it's big of n theta means exact for this algorithm i can't represent the time complexity using theta notation in one line if i use theta notation then i say this algorithm takes theta and in the worst case right that's what i can say about this algorithm because in the worst case when an element is not present it has to traverse after the uh until the end and then it has to realize that element is not present right so the worst case is theta n right i'll have to use the word worst case when i'm using theta notation omega notation is opposite of bigger notation it represents lower bound or exact bound so if we talk about this function see in the best case it's going to take constant time and constants uh when we talk about big o and theta uh theta 1 represents constant and big o 1 also represents constant when you write theta 1 and bigger one we mean that constant right we'll discuss uh these things these notations in detail when we talk about big o and theta but big o one theta one means constant with any notation that you write uh one it means a constant value see omega one since it's exact or lower what it means is it's either constant or any value higher than constant so big omega 1 or omega 1 it represents a constant value or any value higher than constant so if you have a function c 1 n plus c 2 you can write this either as omega of n that will be like exact bound because exact bound is there in both big o and omega so i can write it as omega 1 right omega of n this is how we write the omega notation and i can also write it as omega of 1 this is also mathematically fine because omega means lower as well so what i do is i write the time complexity of this algorithm as omega 1 right and when i say omega 1 it means either constant or any value higher than constant which means this covers all the cases so we are saying it takes constant time or higher than constant that's what we mean by omega 1 or constant right and when we say big o of n that means it takes either linear time or less than linear time here what are we saying it takes either constant time or higher than constant time but which one you would prefer see as we have discussed in the best case average case and worst case we are most of the time interested in an upper bound right that's why omega notation is not used much you would rarely see omega notation in analysis of algorithms most of the time you would be seeing bigger rotation and theta notation because theta rotation gives you an exact amount and big o notation gives you an upper bound and you're most of the time interested in either knowing the exact amount or knowing the upper bound let's now talk about bigger notation as we have discussed earlier bigger notation is used to represent exact or upper bound on order of growth please note that if you know the exact mount you would prefer to use theta notation that gives you more information this is what exact boundaries so main use of bigger notation is uh when you want to represent an upper bound right when you have an upper bound use bigger notation to represent the upper bound so uh there is a direct way of finding the bigger notation for an expression and the direct way is just to find the order of growth and since exact is there in bigger you write the order of growth in bigger notation so uh these are the steps that we use to find the order of growth also so if you see this expression the order of growth is clearly n square we ignore the lower order terms we ignore the leading constant and we get the order of growth is n square and since bigger notation covers exact or has upper bound we can write it as big o of n square right mathematically you can write it as big o of n cube also and four also anything higher because big o of a something means that thing is order of growth wise greater or equal right so we are writing equal here when we know that's equal y to right and upper bound right why to write a higher value so in this expression uh this is a lower order term because we have n log n here right n log n is a higher order term we ignore the lower order terms we ignore the leading constant so we have the order of growth as big o of n log n right let's now see this expression here we ignore the lower order terms we ignore the leading constant and we have order of growth as big o of n cube so this is a direct way of finding order of growth now you see mathematical representation of bigger notation how do we mathematically see bigger notation let's now talk about mathematical definition of bigger notation please remember one thing whenever we talk about asymptotic analysis asymptotic notations we talk about values of n tends to infinite large values of n and that's what you would notice in this definition of we have n greater than equal to n naught so we are talking about all the values greater than a certain constant value n naught for those values this condition should be true f n should be smaller than equal to c of g n then we say f n is big o of g n right so for example if you have f n is 2 n plus 3 you would say it's big o of n so what is g n here g n is n right you would say uh it's big o of n only when there exists a constant c such that 2 n plus 3 is smaller than equal to c n for all n greater than equal to n naught we just need to figure out these two values c and then not and we need to show this thing then we can say this is equal to uh big o of n and we have learned in the direct way that we have this as big o of n right we can ignore the lower terms we can know the leading constant we can quickly say it's big o of n here the intention is to just to show you mathematically also right how does this work so we have g n as uh n and we have f and s 2 and plus 3 now we need to find out two values c and n naught and we need to show that this is always true after uh values of n greater than equal to n naught for that purpose i have taken cs3 now you might be having a question how did i pick 3 see what you can do is you can always take the constant of the highest growing term which is n here right and just add 1 to it right to prove that this is big o of n you just add 1 to it so now you get 3 right so your c is 3 and you need to show that 2a plus 3 is more than equal to 3n for all values of n greater than certain value and that certain value can be figured out by just simplifying the inequality we have 3 is smaller than equal to n now so n naught becomes 3 n naught is 3 and c is also 3 right you can notice that after a value 3 this value 3 n is either greater or equal see if you see 3 itself they are same at 3 this is 6 plus 3 9 this is 9. now if you take 4 this is 4 4 into 2 8 plus 3 11 and this is 12 right for all the higher values this term is going to be greater see why does this work that we always take just one higher value because it's the higher growing term right this is the highest growing term among all the terms we have two terms here and the highest growing term so uh if you keep on increasing the value of n it will dominate over other terms and if you have a higher multiplier this is definitely going to give you higher values after certain value let's now see more examples of bigger notation so here i have written constant values any constant value can be written as big o of one for example hundred log two thousand ten square four ten square eight ten square ten all these are big o of one as long as the value is not dependent upon n there is no n in the term we can write these values as big o one here are examples of big o of n and please note that i have u here u means union see bigger notation means exact order of growth or higher order of growth so we can cover these terms also they and they both these both terms come under big o of n right so constant also can be written as big o of n but ideally you would not write them as big o of n you would write them as big o one when you know that it's exact uh constant growth you would write bigger one notation and in fact you would not use bigger notation for those purpose you would use theta notation right ideally you would use theta notation when you know the exact order of growth so here are examples n by four two n plus r three uh if you ignore the lower order term ignore the leading term constant you will get these order of growth as big o of n right now this is a lower growing term this is log n and log n is smaller growth than n still we can write it as big o of n but ideally we would write it as big o of log n or even better would be theta log n when we know exact order of growth we would write using theta notation not bigger notation these are just to explain you mathematically so let's see this example uh in this example in this series we have all the terms that have order of growth of s n square and we can write all of these as big o of n square and we can write these also as big o of n square but again ideally you would like to write the exact order of growth you would like to write this as big o of n or theta of n this is theta of log n or big o of log n bigger notation works for multiple input variables also for example if you have hundred n square uh plus thousand m m and n are two input variables what we do in this case we again take the highest growing terms so n square is the highest growing term then for m this m is the highest growing term so we write n square plus m as the order of growth let's see this example m square is the highest growing term for m right for n we have two terms n and m n and m n is obviously the higher growing term right it's multiplied with an input variable we talked about m test two infinite n tends to infinite so we have uh m square plus m n s order of growth of this expression let's now talk about applications of bigger notation please remember one thing whenever we have exact bound whenever we know the exact bound on order of growth we should prefer to use theta notation why to use a notation when gives which gives you a loose information say if you have an algorithm like finding maximum in an array right you know that whatever input you provide you are going to traverse through the whole array right and you are going to find the maximum by traversing through the oval array so it's always going to take an order of growth so why to use bigger notation why do you say big o of n you can better say it's theta n algorithm to find the maximum in an array or minimum but many times you have complex logics right uh when you're implementing algorithms or when you're writing some business logic you have complex inputs which has many ifs conditions many termination conditions in those cases what you do is you try to figure out the innermost statement the statement which is being executed maximum number of times you find an order of growth on the number of times the statement is being executed and then you say that's the order of growth of this algorithm in terms of big o basically you consider the worst case of the algorithm right and in the worst case you find the order of growth and you put it in bigger notation and then you say this is the time complexity so you have put an upper bound it's easy for you to get an upper bound many times rather than knowing the exact amount let's take an example to get an idea here is an example for a of a function that checks whether a number is prime or not so the syntax that i have written here it's close to c c plus plus and java the only difference in java is you will use boolean instead of bool so this function what it does it checks whether a number is prime or not and we are going to discuss detailed working of this function in the mathematical track where we have discussed prime number checking video right we are going to discuss in detail how this function actually works [Music] the idea here is to understand an application of bigger notation with the example of this function see what this function does it checks whether n is 1 or n is 2 or n is 3 these are the corner cases if n is one then it returns false one is not a prime number if n is two or three then it returns true they are prime numbers now it again has an optimization if n is a multiple of two or n is a multiple of three then also it immediately returns false so if you provide a number like 100 200 500 which is an even number it will immediately return right or if you provide a number which is a multiple of 3 then also it will immediately return right it would not go inside the loop for other numbers it will go inside the loop and it will go till square root of n we have the condition i into i is more than equal to n which means i is more than equal to square root of n we will discuss this logic in detail in the prime number video and what we are doing we are doing i equal to i plus 6 so what is happening here uh there might be many situations where we do not run till square root of n for example if you talk about the number 65 right square root of 65 is going to be above then eight right something beyond eight right eight into eight is 64. now uh but what will happen here in the first iteration itself you will return false because 65 is a multiple of five so if you taking constant time but in the worst case when your input number is square of a prime number in those cases this is until square root of n right so you are going to run square root of n minus 5 divided by 6 ti