Time and Space Complexity - Strivers A2Z DSA Course

hey everyone welcome back to the channel I hope you guys are doing extremely well then this lecture we'll be learning about time complexity and this is the continuation of Strivers A to Z DSA course slash cheat so uh if you remember in the previous video we have covered all of these green TIG Mark things and this video will be covering the time complexity learn Basics and then analyze the next steps what does that mean they'll be teaching the basics of pen complexity what is time complexity how to compute time complexity and all the terms related to it and then eventually when you go through all the latest steps at every problem that we solve we will be discussing time complexity of every problem in depth So eventually when you complete all the steps or all the problems you will have a very very good hold on the time complexity part now in this video I cannot teach you time complexity of uh very complex codes because you do not know them right so once you learn the complex codes and recursion backtracking we will be discussing time complexity in depth over here but as of now just let's start with the B6 so the first question what is time complexity now what why is time complexity required first of all now whenever you're going to an interview you might end up writing a piece of code right now that code how do how does an interview judge that code this is where they will analyze the time complexity of the code now they will not they're not going to take your code run into a machine and see how much time does the machine take and on the basis of that tell you that your code is right or wrong that is not going to happen this is where something like time complexity comes in whatever code you are going to write in an interview in every interview they're going to analyze you what is the time complex team and what is the space complexity and then on the basis of that you will be judged right so whenever you write a code that might end up taking let's say two seconds on a machine or might end up taking three seconds on a machine might end up taking five seconds on a machine so the time taken will you call it the time complexity no you will never call time complexity As Time taken now you might ask but why if a code is taking certain time that should be its time complexity let's give you a very very easy example to explain why not imagine I take this code I take this code this can be any code any code I take this code and I run it on two machines one is the old Windows machine and the other one is the new Macbook machine now I'm sure the old windows hypothetically might end up taking two second to run that code while the new Macbook which is a lot more in terms of the like a lot more latest in terms of the configuration might end up taking one second so does it mean that your code is taking one second or does it mean that your code is taking two second it might happen I bring up some other machine the next day it might end up taking lesser than one second so depending on the system the code ends up taking a different time so that is why time complexity cannot be said as time taken because it is dependent on system it is different dependent on configuration right so this is why that is this is the first point time taken is never equal to time taken never ever so you might ask if time complexity is not time taken then what is it that is where I see the definition the rate remember the rate at which the time taken increases the rate at which the time taken increases with respect to the input with respect to the input size rather so what does that mean let's explain this with the help of a graph so again let's take the same example where I'm saying I have a old Windows machine and I have a new Macbook okay now imagine you are giving the old windows a size 10 just as hypothetical a size 10 input size and I'm plotting the graph and this is one second this is two seconds this is three second this is four second this is five second this is 10 input size is 20 30 40. at 10 input size it might end up taking 2 seconds at 20 it might end up taking 4 at 30 it might end up taking 6 which will be here so you see the time increasing at some at some Theta angle like it's increasing at a certain slope so this increase this increase this Theta angle is what you call as the rate of increase this is what you call the rate of increase okay now let's see the new Macbook so if I take the new Macbook the 10 might end up taking one second the 20 might end up taking two second the 40 might end up taking three seconds so it's here here so this is the read and this Theta is the rate for the new Macbook so I can say the rate at which it increases time is what you call As Time complexity depending on the input if they are giving you more input it might end up taking a certain more time so the rate at which the time increases is what is generically referred as time complexity of Any Given code the next question that might come to your brain is okay if we are saying the time complexity is not computed in terms of seconds or minutes then how do we how do we write it this is where something like a big O a bigger notation comes in now in all the interviews that you're going to give or in all the examinations if you're writing a piece of code they will ask you to analyze the time that is when you do not like you will not say two seconds no you will say it in terms of bigon notation every piece of code takes time in terms of Vigo notation what is Big annotation I just give you a prime example so it's like a capital O open parenthesis and a closed pattern this is what bigo notation is and inside it you write whatever the time is taken inside is you write the time taken or the hypothetical time which I'll show you how to compute let's take a very very small example to compute the time complexity of a certain code so imagine I write the for Loop I've already taught you Loops in the previous video I equal to 1 I lesser than 5 I plus plus and then I write C out and my name Raj okay so can you tell me what is the Big O of this this is nothing but the number of steps that this code will take first step is very sure assigning the second step is comparison the third step is printing right and then you come across and this is your fourth step and then again you check this is your fifth step and then again you print this is your sixth step so this is how every step is computed so whatever is the total number of steps that is what you write inside is and that is what you call as the prime bego notation but you cannot just keep on Counting step one step two step three step four step five step six step seven that is insane you just cannot keep on manually counting the steps this is where three rules come in and I'll write the rules the three rules are very simple always compute time complexity in terms of worst case scenario time complexity to be computed in terms of worst case scenario why was case I'll explain you the next one is avoid constants avoid constants the third and the third is avoid lower values so if I have to compute the time complexity or the Big O of this piece of code let's look at it on a very high level can I say this for Loop is running for 5K I can at every time what is happening it's like increment check print increment check print so can I say for every time it's operating price but every time it is operating three times increment check print five into three can I see this I can so can I say a total of 15 times that is how you write it you write it as we go of 15 is what you write and this is time complexity it runs for 15 times but this is a number this is a number you generally do not represent your code in terms of numbers okay so let's let's change this now can I see this if I change the statement if I if I probably will change this to lesser than n less than equal to n now can you say how many times will this Loop run I know one thing this is going to run for we go of n times the loop the code will run for n times n iteration and at every iteration one two three things will happen that every iteration three things fella pretty obvious this is what will be the time complexity we go of t n we go of 3n will be your time so whenever you're saying we go you go to the code and you see how many times it is running and then you write we go of 3 n as your time complexity does that make sense right okay let's now come back to the three points that have written always compute time complexity in terms of worst case scenario now there are three things one is the best case one is the average case and the other one is the worst case now let's take a snippet of the code and explain you what is best case what is average case and what is worst case okay let's so this is the snippet of the code now imagine the snippet of the code is very it states of marks is lesser than 25 print grade D it states of marks is less than 45 print grade C if marks is lesser than 65 then you go ahead and print Grade B or else you go ahead and print create a so let's talk about the best case scenario what is baskets when the program takes the least amount of time so over here can I say if someone gives you an input of marks equal to let's say 10 what will happen this will execute it and grade D will be printed and none of these lines will be executed none of these like so can I take can I say the number of operations will be just one a check and a print which is like two operation which is like two operations and I said imagine if I give you marks equal to 70. so at Max 10 it was we go of 2 operation correct we go off to operation now if I give you marks equal to 70 what will happen check false check false check false it comes here 3 and then four can I say four operations were here like one two three and then goes to else somewhere around 4 octave so it takes four operations so whenever you're analyzing the time complexity will you say that my code runs in week of or will you say that your code runs in week of four obviously you will say we go for because that might be the worst case that the computer might encounter when it is given an input so always yes always compute the time complexity in terms of worst case scenario and if they will ask you the best case you know the best case whatever is the best case like in this case is the first if statement getting executed which is we go of two operations so you've got an idea about the best case and the worst case you know what is the average case there's nothing but the best plus worse and divided by two it's it's the median of it so pretty self-explanatory why if I give you a question why do we compute it in terms of worst case the answer is again self-explanatory if you're building a system will you build it for one person or or will you build it for one million person if given an option if given an option he will say 1 million because you want to build a system which can scale up you always think of the worst that can happen that is why when I talk about time complexity your code extreme worst case is what is considered while Computing time complexity now let's talk about constants I'm saying avoid constants why am I seeing that let's take a shuttle example let's say something like 4 n Cube something like 3 n square plus 8 that's it so over here 4 n q plus 3 n square plus 8 these are the number of operations that your code is taking hypothetically I do not want to be support I'm just taking a hypothetical we go expression now imagine if I tell you that the input size n the input size n is somewhere around 10 to the power 5.

right I'm saying 10 to the power 5 is the input size so when I say 10 to the power 5 and you put that in What will what will it be 10 to the power 15 10 to the power 5 Cube 15 plus 3 n Square that's 3 10 to the power 10 plus 8. tell me a very easy thing 10 degree of 15 plus 10 to the power 10 into Plus 8 will this 8 have any significance in the operations this is in itself such a huge number if you had eight will it will it matter to them like whatever is standard of 50 I'm not sure what it is it's a billion trillion whatever more than that I guess with that A Plus 8 does it have a significant it doesn't if you're earning 1 million and I give you one buck that will not have any significance that is why we do not consider constants we do not consider constants now in terms of code imagine I see you something like this int x equal to 2. so this is the modified code this is the modified code x equal to 2 and then the for Loop so this is one operation it's it's something like n into three plus one the time complexity updated will be n into 3 plus 1 operation and this is the one operation so you never ever take this unit operation so you will not consider this you will say no it will still stay as n into 3 I will avoid constants because whenever the input size is very large those constants have very less significance got it now let's take the next thing avoid lower values let's take the same example I am saying 10 to the power of 15 10 to the power 15.

if you add 10 to the power 10 to it will it have any significant it won't so adding 10 to the power 10 to 10 to the power 15 10 to the power 15 will have absolutely no significance it is similar to saying I will add let's say one two thousand maybe even lesser than that it is similar to actually seeing one two yeah I'm adding one to this much or one more zero yeah will it have any significance no so adding this one to this one will it have any significance no the number of operations will be like slightly slightly more because 10 to the power 5 15 in itself is such a huge number but this is why again certainly very important avoid the lower values which does not change its significance by much so avoid lower values correct so these are the three points that you will always keep in mind while Computing the Beagle notation because Vigo notation is what you will be expressing your code in interviews always all the problems that I'll be solving I'll be telling you about bigo notation only apart from bigot notation there are certain other terms at Theta notation Omega notation Delphi a lot of other terms in textbooks are they required in interviews no no one is going to ask you these things no one or just for knowledge let me tell you the bigo notation is always the highest complex or the worst case complexity remember this worst case complexity or the highest or generically known as the upper bound complexity it's known as the upper bound the Omega is the lower Bond as I said the kind of the best case is the lower bound or the lowest Bond or whatever you can and this is nothing but the average complexity foreign just a quick disclaimer there are a lot of theoretical stuffs revolving around Biko Theta Omega a lot of limit derivations but I am not teaching you Theory stuff I'm not teaching you for your semester examinations I am teaching you for interviews I am preparing you for the DAC coding rounds and they will not be asking it over there they'll be asking a programming logic you'll have to solve problems don't be asking you tell the formula for big connotation in limit terms no one is going to ask might be asked in semesters for that you'll find different teachers on YouTube if you are learning from me you're learning for interviews for coding rounds for problem solving abilities not for your semester exam so please do not comment that you did not teach the mathematical derivation because that is something which is not required while problem solving right so you know how to compute picona let's uh do one thing let's quickly solve some questions okay so the first snippet of the code for which you have to find the time complexity imagine inside your main you have something like int I equal to zero I lesser than n i plus plus and for INT J equal to 0 J lesser than n j plus plus and imagine it has a block of code like something a single line of code and this is your entire snippet of the code okay this is your some block of code you can consider this to be taking very constant time constant time so this can be avoided tell me the time complexity you know time complexity will be computed in terms of bigo notation tell me the time complexity of this particular code pause the video and maybe think about it and then see if you are correct or not so how do you analyze the time complexity of Snippets of the code it's very simple analyze how's the code working so if you see the outer loop is starting from I equal to 0 and going till n so it's definitely running for n times and the inner loop is going from J equal to 0 till n this is also running for n times now if you're a beginner you might find it a bit difficult so what you will do is you will say at I equal to 0 what is happening let's see whenever I is 0 what is happening whenever I is 0 it goes inside and J starts its value from 0 and goes till n and this completes n iterations can I say when I is uh zero J goes from 1 0 1 2 3 dot dot till n can I see that and then again when the is value increases to one can I say J again goes from 0 1 2 3 because it's inside it it's reiterating again from zero can I say if I is 2 again it again goes from 0 till n can I say till I is n minus 1 y n minus 1 because it is lesser than n can I say it again goes from 0 till n minus 1 to be very accurate can I say this so what is happening every time it is running for n n every time it is running for n and n so can I say it's running for n times first then for another n times second time then for another end time second and then dot dot dot till end times how many times is it running can I say it's running for exactly n times so can I say this is nothing but n into n yes thereby n square is the number of iterations it is taking yes there are other things as well like increase comparison we usually do not consider which rule avoid lower values if you remember because 3 into something won't matter that much because you can avoid it so what I can say is it's running for n Square yeah if you want to consider all these constant operations you can do it that is your wish I usually do not do it so we go off n square is what is the time complexity of this particular let's say the next example and try to compute the time complexity of this one so it's like the first Loop is definitely running for n a second Loop is running from 0 to I so let's analyze slowly and probably we'll get the time complexity so can I say if I equal to 0 J is nothing but from 0 is only running for 0 can I say this because when I is 0 J is running for 0 K lesser than equal to 0 it will run for just one time 12. when I becomes 2 what happens J now runs for 0 sorry when I becomes 1 rather and I becomes one what happens J now runs for zero and one can I say why because I is 1 it's like 0 lesser than one correct nice can I see if I is equal to 2 what happens J now runs for 0 1 2 so when I at the end becomes n minus 1 what will happen J will be 0 1 2 dot dot n minus one can I see this is how many operations it is taking again I'm ignoring all these constant operations I'm taking the overall iterations now first time it's one equation next time it's 2 x m is three four until n so can I say the number of iterations the first time it is one the next time it is two the next time it is 3 and X7 is 4 so on Del Nitric can I see and do you remember the formula for this particular thing some of the first and natural numbers simple maths n into n plus 1 whole divided by 2 which is nothing but n Square by 2 plus n by 2 thereby this is the exact time complex but we can avoid if you remember the rules constant to be a like the smaller values to be avoided so it'll be like n Square by 2 so this is the time complexity again if you try to remove the constants like one by half you can say the time complexity is near about we go of n square but if someone does ask you the exact time complexity this is the exact time complexity but according to the rules this is voted boils down to so these were the basics of time complexity okay now next I'll be doing all these patterns in the next lecture well be writing all the nested for loops and there you can analyze time complexity in a much better way but eventually all the time complexity terms like login and login n Square n Cube n Square login all of these things you will see as I proceed with the playlist I do not want to rush you in I just want you to get an overview of what is time complexity how to think on it how to compute how to avoid terms these things should be crystal clear to you so I'm assuming the time complexity uh stuff is crystal clear to you they'll now be moving to something like space complexity again what a space complexity it's the memory space that your program takes it is the memory space that your program takes in a very very naive term when I talk about memory space again it will vary from machine to machine so you cannot be dependent on the machine and that is why again in order to complete base complexity we will be using the bigo notation again so bigo notation is kind of very very important in all the interviews we go in terms of time we go in terms of the space so we'll again be using bigger notation and you know the reasons why not in terms of KB MB GB Etc so what is exactly the definition of space complexity it is nothing but auxiliary space Plus input space what is auxiliary space the space that you take to solve the problem the space that you take to solve the problem input space the space that you take to store the problem foreign not the problem so let's give a very very small example in order to explain what is auxiliary space and what is the input space so I'll write a very very small thing imagine I am taking an input of A and B in Java you know how to take it and C plus plus you know so I'm assuming I'm taking an input of a uh so I'm not writing any syntax because then it'll be C plus plus or Java specific I just want you to learn pseudo code and the logic so in Imagine a given input to variably imagine I give an input to variable B and I am saying c equal to a plus b now I am saying c equal to a plus b so the auxiliary space that you're using is an extra C variable this is the auxiliary space why because you're using a c variable in order to solve the problem okay you cannot use that is okay I am saying if you use any extra variable or extra space to solve the problem that is what you refer as auxiliary space what about the input space this is one and this is one so both of these can be referred as input space whereas this can be referred as auxiliary space and combined I can say this is the space complexity or I can say we go off three over here because you're using three different variables you can convert them into bytes if you're taking an integer you can convert them into bytes I am not concerned about this in an interview you will have to say it in terms of bigo of something not in terms of bytes KB MB so for example if I Define an array of size n it means I'm consuming B go of n size or n space complexity so in an interview if you are solving a problem which uses an array of size n you say bego of n is the space complexity that I am using as simple as that now a thing that I want to highlight over here is if you're doing space complexity a lot of times it will happen is imagine you're given an input to a imagine you're given an input to B and the task is to some add both the numbers a lot of people say I'll do this b equal to a plus b so the summation of a plus b will be stored in B and I'll not be using the third variable it is okay to do it is okay but this is something you should avoid it takes lesser space but in an interview the interviewer will say this method is not done why is it not done this thing in person in perspective of software engineering imagine you writing a quote for a big MNC and they're giving you some data they've given you some set of data and they want you to do something on that data and you're like you manipulate the data over here you change the data you changed B this is why never ever do anything on the input very very crucial rule in interviews never do anything to the never do anything to the input unless the interviewer sees anything to the input because data should not be touched you can do whatever You Wish by taking the data what you cannot do on the data because if you manipulate the data it has an issue because in software engineering that data might be used in some other place so never ever manipulate data this might save you a bit of space but the interviewer will end up rejecting you because this is a very very bad practice so never ever do anything to the input given always take extra variables extra array extra Matrix it might be tempting that if you use the same input variables you will end up taking less of space but it's it's not a big concern if you're using bigo of n space like if 2N is used by taking an extra array it is okay this is okay no one is going to reject if you're using big of 2N instead of B of n if the interview specifically says do it on the input then you can use them otherwise do not and you can tell that to the interview you can explain that I do not want to uh I do not want to tamper with the data that is why I'm taking an extra variable in order to solve this problem keep this in mind forever so this was about the high level idea about space complexity and the practices you should follow regarding the in-depth knowledge when we solve different problems on different data structures you will see how I'll be explaining space complexity in terms because the more problems you solve the space complexity gets into your head in a much much better way so before ending up this lecture in case you are into competitive programming then remember one thing over there you do not run your codes on your MacBook or your windows whatever code you write you send it to the server there is a server you send it to the server everyone sends to the same server and these servers in competitive programming or let's say you're using lead code or let's say code Studio or let's say gfg any platform if you're using they have their servers and most of the servers take one second for 10 to the power 8 operations remember this most of the servers most of us are take one second for roughly 10 to the power 8 operation might be 10 to the power 8 plus something might be 10 to the power 8 minus something but roughly it is 10 to the power 8 operations is what you can execute in one seconds on the server most of the servers are relatively the same and if they're saying two seconds it doesn't mean 10 to the power 16. it doesn't it doesn't it means 2 into 25 operations if they're saying five seconds it means 500 to The Power 8 operations do not do 10 to the power 8 to the power of to not a lot of people do that okay so this is something just keep in your mind because a lot of times you will see time limit one second they'll write it they'll write it in your uh let's say coding round the time limit given to you is one second where you should Analyze That the time complexity of your snippet of the code or your entire code should be roughly big go of 10 to the power 8 operations if in a coding round they are stating time limit one second it means roughly when you compute the time complexity of your code avoiding constants avoiding lower values it should be because of 10 to the power 8 operations so with this I will be uh completing the step 1.