Tutorial 7-Competitive Programming-Find The Time Complexity Of This Problem

Key Takeaways

hello all my name is krishnak and welcome to my youtube channel so guys this is the next tutorial of competitive programming along with data structures and algorithms and in this video we are going to discuss about a problem statement which is based on time complexity so many of you have actually given me a feedback saying that krish first tell give us the problem statement give us some time around five to six hours then we'll try to solve it we'll try to provide that particular comment in this specific video and then you try to provide the solution so considering this i am starting with this particular thing guys here first of all i'm going to discuss about the problem statement after discussing about the problem statement the next video will be the solution of this particular problem statement okay so in this video we are going to find out what is the time complexity of this particular function so here is a function which i have defined as def func with n value over here then i write for i in range 1 comma n this is a for loop first for loop n value can be anything whatever you want to specify then j is equal to i i is basically getting assigned to j then again i have an internal loop which says that while j is less than i multiplied by i then j is equal to j plus i if j modulus i double equal to 0 for k in again another loop after the if condition for loop is again there which is iterating between 0 to j and then i'm printing crash okay now this particular problem statement if i write funk of 1 so here you can see that nothing is getting printed if i write funk of 2 i think ok nothing is getting printed over here again if i write funk of three over here four krishnas get imprinted if i write funk of four this many krish is getting printed now the main problem is that you need to find out what is the time complexity i've already shown you whenever we ask what is the time complexity you should basically be getting your worst case or the best case you know what is the time complexity but in this example i want the worst case of this particular time complexity and for this i have also given an options over here capital o basically denotes the big o notation which is nothing but the worst case for this particular problem statement with respect to the time complexity the first option is worst case o a bigger notation of n cube second option is bigger notation of n square third option is big o notation of n to the power of five and the fourth option is big o notation of n multiplied by n minus one remember this is the worst case so you have to tell me that out of this all option which is the exact right option you can tell me and you can let me know about it again remember we are talking about the worst case okay try to do with different different n values you will definitely be able to get the solution okay please try it out again this is the pattern that i'm going to follow with respect to all the other videos that are going to come up with in competitive programming this is a very very simple function right now in the later stages i will be creating more complex functions there will be so many conditions internally and you basically need to find out the time complexity uh with respect to the solution because this is also that is basically getting asked in data structures algorithm this kind of problems was asked to me when i had given uh interview in yahoo uh somewhere around 2013 okay uh this kind of questions were actually asked i could not clear the interview i went till second round in the third round um they asked too much extensive data structures and algorithms questions uh with respect to different kind of sorting techniques yeah sorting techniques i knew most of them but yes they were trying to you know drill down a lot of things from me so this kind of questions will definitely be helpful so just try it out from your side and uh in the next video probably after five to six hours i'll upload the solution for this right i'll explain you with my pen i'll try to write everything and then we'll try to understand it so i hope you like this particular video please make sure that you subscribe the channel and please do comment down the answer for me out of these four options and this particular notebook file will be uploaded in the github i'll see you all in the next video have a great day ahead thank you bye-bye