Before Solving Some Questions of Time Complexity I will tell you some tricks to get rid of time complexity. after that we will do some set of questions. which will make you a very good grasp in such questions. due to the time complexity. So here first of all i will talk about the time complexity of any algorithm when you have to find it so what is the first step that you do and at the same time how to approach this problem, That I am going to tell you people. So here first of all I would like to talk about what is that reason And quickly we will talk about the basics as we have already talked about it: If you haven't accessed the playlist, be sure to check the data structures and algorithms. So here what i will do, i will write the tricks and write the first technique, I will not waste much time The first technique to find out the time complexity is: that you drop the non-dominant terms, okay. Drop the non-dominant terms You drop whatever non-dominant terms you have What does this mean suppose you are given a for loop OK, I'm writing a for loop: a simple for loop. for(i=0; i<n; i++) This is your (n) times running for loop: It is written in (c) language And above I have also written (n) time, let's assume (i=0; i<n; i++), okay Now this for loop is doing some work So first of all what you people have to do, whatever problem you are given to people you have to break it into fragments. And in one fragment you get some time Suppose here is happening (int), (int) not inside the for loop (k=i) is happening over here, something (k) will happen above And I'm just trying to make a sample program here And the same thing is happening here (k++), let's say that's just happening, anything else is happening!! Let's say (x=y+1) is happening and it's going on inside the loop. So what will happen that this thing:? Does it dependent on (n), It does not dependent on (n) So let's do it, whatever work is going on inside the for loop. it will be the same every time, because it's not depending on (n) Now the value of (i) is increasing, but let us assume that the portion here is, (k) is taking time. Suppose it takes (k) time to run which are the statements inside it How many times are these statements being run? It is running (n) times, because this loop is running (n) times Okay. So what will be the time!, If I get time for the algorithm, then then it will be (kn), okay. So it will be (kn) Now here it will not be equal to Exact (kn), but will be very close to (kn) Why wouldn't exactly be equal? Because when the value of this (I) increases, it will make a difference in some time. So we ignore that thing We're here to assume that that's all the steps. k=i, k++ and x=y+1 In this way, whatever instructions are going on here, it is taking almost (k) time, on and average (k) will be same either above or below So that's why we took it as a constant (k) Now the time taken to add 1 to 2, and add 2 to 4 when you hit the exact time, would be the time it took to add 2 to 4 will be different when 1 to 2 is added to its time. But we ignore that, We believe that these operations are all (k) time consuming This for loop, that is, how much time is being taken for this fragment It seems (kn), okay So before this (int i) would have been written here, (int k=0) would have been written I'm just guessing, there will be some code above, ok And that code has nothing to do with (n) So what will I do, I will write here (k1), as if he is taking time (k1) I take this for (k2) here, I accept this (k1) So I will say (k1+k2n) or (k2n+k1) it is taking time to run my entire code. ok, this whole code has to be run Now see what will happen here, this whole code is taking (k1+k2n) time to run What I said here were drop the non-dominant terms When I talk about time complexity I believe that whatever (n) happens, will be huge. because a sufficient, sufficiently high value of (n) is taking I told you in the definition of big O (n=n0) is quite high: So we do Time Complexity Analysis for huge value. when the value of (n) will become very high When the value of (n) becomes very high, then out of (k1) and (k2n), (k2n) which is the larger number will be So we won't compare these two, and we'll drop it We will say that (k1), when (n) is really very high in front of (k2n), then he will not be able to stand And (k2n) it will be time, okay So far I have only applied (k2n) After that there is a second role to preciously describe big O. Drop the constant Drop the constant term Okay Drop the constant term Now what will happen here, I will remove the constant term then it will be O(n) So once the for loop is running over here, and that (n) running times, (i) is running for n-values, O(n) Because as I keep growing (n), this work will happen so many times more if (n) is 3 here, then this loop will run 3 times then (k23) Similarly, if (n) times will run then (k2n) and here I have O(n) found it. found O(n), Okay Drop the constant term The third technique that I want to tell you is this: That break the code into fragments Okay Break the code into fragments i'll give you an example Fragments and why we broke in fragments? See, let's say a loop is going on and let's say another similar loop is going on Which will work for (i = 0(n)), I rub it a bit, okay i rub it Suppose this code is not ending here and another for loop in this code: it's something like that, for(j=0; j<n; j++) A lot of people who make mistakes know what they do Let it have (k=i+1) or suppose there's (k--), okay What many people who make mistakes will they do, (n) look here, (n) look here and will say it's (n²) and it isn't (n²) And why it is not, how to know, what is it, I will tell you Look at the work being done on it, it is as if it is a complete code file. I have to find the snippet time of this algorithm first i will break it into fragments The first fragment turned out to be this one, with a little bit of initialization It took constant time, because it is not such that if the value of (n) increases, then its time will increases. (nth) Time is going to be (nth) Time, isn't it? even if I walk for him (n = 10), whether I will go for (n = 100), whether i will go for (n = 1000) So it will only take a constant time, I assume that (k1), that the time it is taking in running, it will be constant it will be constant, ok After that the time it took, the inner part, that too will remain constant, I have accepted that (k2) I am not talking about the outside of the for loop, I am talking about the work inside, that will remain (k2) And I have accepted it (k3) within the work that is being done, okay. what to see now If I want to find out its time here, how many times it is running then i will write (k1+ k2n+ k3n) Because this is also (n) time running, and this (n) time is being run Now what will I do with this rule! remove the non-dominant term Now taking (n) common from this, n(k2+k3), which is a constant I will accept it in (k4) and (nk4) I will do it, and it will happen O(n) Why did this O(n)? this O(n) happened for this Because I put the rule, drop the constant term Drop the constant term eliminate the constant term, ok Eliminate Constant Term So I dropped the constant term, so here's what happened (k1+ k2n+ k3n) (k1) removed from it first, (n) taken as common (k2+k3) persuaded (k4) and then O(n) So if there is a different for loop then that too takes O(n) , if you will also add one more (k4) If you do it (k=0), (k<n) and if you look at it, it will come out O(n) Okay, it will not (n²) ok remember you this thing Now I want to take one more example which is important So here I am taking one more example, after that we will solve the question It is not that we will not solve the question. But by taking an example here, I want you to understand that how these problems are approached, Okay. So this which is our for loop, I will build on it only So I'll make a little space over here On top of this, suppose (k1) it is taking time, whatever code we wrote, I will keep it above. And down here I'll put another for, on top of it suppose this is nested for loop (i=0; i<n; i++) And inside this for loop there is another for loop, let me make it (j) Let me make it (j), okay And at the same time, here's what I'm (j<n) doing, it's going to (n) times, its this off, its this off, okay. So whatever this is it's inside an else for loop, so it's a double nested for loop Inside the for loop is the for loop, okay I should have become a intend, for starts from here, looks a bit good But you understand here, how will it be if I make some space here? If I start from here for, so there's this loop inside it, okay Now tell me how it's time complexity will come out If you see this and say that this too O(n) is like the previous one So it is not O(n) I will tell you why it is not O(n) What do I have to do, I have to get out T(n) what I told you guys There will be some code on it which will take (k1) Now I have become so smart, by doing questions, and you will be done too That (k1) it is will going to be non-dominant, if constant is being added then we will remove it, okay So this (k1) does not make any sense, but even then I will write one more time. We will ignore this (k1) again in questions, I will not tell again and again So now you have understood that if a constant is being added, Time, do not take it. okay. And why not take it, we have seen it because it has to become non-dominant like that later So (k1) and now after that (k2) is working but how many times this (k2) will run Okay. so how do i find out so (k2) will work, but how often it will have to be seen here And how will I see (k2), and how many times it will run So once the value of (i) will be zero(0) Ok, So once the value of (i) will be zero(0) and then the value of (j) will be zero(0) So once so (i=0, and j=0) will run for Okay Then the value of (i) is zero(0), since the first inside loop will run, once the value of (i) is zero(0) then (j=1) will become Then (0,2...n) then it will go on till (n) So once the value of (i) the (n) times are running out, watch carefully, watch very closely Then later I will ask the question, then I am telling if it is not done. value of (i) will be zero(0), and what is happening after that, (n) times running then the value of (i) will become (1), it will run again (n) times Then the value of (i) will be (1), (n) the times will run So what will happen over here, it's running (n) times, for (i=1) Well, for (i=1), it's running (n) times and then it is running (n) times, for (i=1), for (i=0) For similarly (i=n) it will run (n) times too, ok And when (n) you will add (n) times, what will come When you add (n), (n) times till n(1+1+1 and i=n), ok It will be (n-1) because I am taking the index (i=0) then (i=n-1) will be and here is (n-1) So it's going up to zero(0) to (n-1), it's okay So if you would do (n) times, it was for (i=0) then how many numbers will be in it! (n) will remain then it will be (n), it will run for (n²) times is it clear to you guys I didn't want to say directly that this will run for (n²) times This is what you guys should know, why it will run for (n²) times Because look at the value (i) of zero(0) for (n) times it will run Then for the value (i) of (1), (n) times will run Then for the value (i) of (2), (n) times will run Then for the value (i) of (n), (n) the times will run When it was going on (neither) times, went on doing it (+n) in the same number of times Well, I am doing add only in as many times as it is going on here. So that's why it will be (k2n²) it will be (k2n²) So how did this happen (k2n²), this is beyond the scope of this course, it is very pure and simple mathematics But even then I told you guys If it's not clear to you why it will work (n²) times So I'd say let's go look at it for 3 and 3 and print here (i,j) and make a count variable and count it, how many times it is running You write (c) program, write in Python, write in the Python, write in Java, write in the Java But when there are 2 loops inside one, then that will run for (n²) times And if another loop is given inside it, then it will run (n³) times And if another loop is given inside it, then it will run (n^4) times Okay Because this you guys should have clarity because many times you will get to see such patterns. Then you will not sit down to do this, I have got you to understand what we are doing, okay. So now seeing such term should not take you so much time that you are saying that it is non-dominant This is Constant, O(n²) is Tell me as soon as you see it, let your eyes ignore it. And by looking at the bigger term, take the term with the highest degree: It will be O(n²), okay. So this is the simple technique that we will use that It's not much technique, it's just 2-3 techniques: read the definition of big O, big Theta (Θ), and big Omega (Ω). That was just for clarity Here the work has to be done for this Okay from here the work will be done. There are some more cases in which what has to be done when there is a recursive call then we have to count the recursive call So it takes a little effort over there But, but what happens What is the answer of big O, you people get out, when there is AIM then we approach the problem in a different way. I will solve some problems for you guys. Here were the tricks that I told you guys that If there is a double for loop, then it becomes straight (n²) But never solve the question blindly, because you people can be trapped. Maybe he can put a recursive call inside it, to complicate the query a bit Those kind of questions are a bit high level, but we will do that too. and will increase the level, go a little above from simple questions So let's solve the question, it is very important Alright Guys, now the time has come to solve some problems And I have kept a complete set for you guys here. If you haven't accessed this playlist yet Which playlist, data structure and algorithm's playlist So make sure to access it man Because all the videos are going to come on this, I will put all the videos on this And what am I going to do here now? I will solve the problems which I have shortlisted for you guys. and i am using one note here, a lot of people ask which software do you use it And I blow up in the editing, which is the part above, that's why you see so much In some videos you guys ask what software is this so it's okay I'm not flying it now I hope I will be able to explain you better here, in one note What is here that I have made a notebook, in one note, and the document which is here, I will convert it to PDF anyway I have handpicked some questions here which I am going to give to you guys here. And I have also given their programs to you. so you see here I have opened this folder, in visual studio code So you people will come to know here. that I have also made some programs. And along with that, I have created a folder named Time Complexity here. inside which I have put this one note notebook. ok so i have given this question here very clearly then there should be no problem. So I'm here, back, in my one note notebook And let's tackle the first question, and I have kept the programs of the questions which are here. So what will I do, i will do close to the right And you guys see the program of the first question here, and first of all see what this question is saying. So this question is saying that Find the time complexity of the function (Func1) function in the program shown in program1.c as follows, okay So by a program1.c is a file What is this file? It has a function and it is (c) program obviously Since I am doing in (c) language, if you do code analysis in Java, Python or any other language then the steps will be the same. Because even if you come from another programming language nothing is going to be change Because data structure is algorithm, it is a study that does not depend much on programming language. Because in that study, the implementation will be different in different programming languages. You Can Totally Follow If You Are Using other Programming Language So here I will set a pen, and here what I will do i will solve this problem So it's saying that Find the time complexity (Func1) function in the program shown in program1.c as follows So what's in here is a function by doing (func1), it's an array and this is the function by doing (func1) and what is this array doing It is passing the array (func1) to the array, and see what (func1) is doing with that array So here int sum=0; is coming by writing, and here product=1; is coming by writing So basically it is calculating the sum and product Look, if you look at it, there is a skipping of the array, which is 3 and it will go from zero(0) to 2(n-1) here this loop Just like I told you a while back that when you have to analyze an algorithm, first of all you break it into fragments. So what will I do that I will break it first in this fragment And I'll name it as (F1), ok So I named it (F1), I will name this fragment as (F2) I'll name this fragment as (F3), ok So we've got 3 fragments now F1, F2, and F3 so the time of (F1+F2+F3) will be that I will take as the overall time of the whole function What will be the time of (F1), some constant will be because you are doing sum = 0 and product = 0 each time It is not depending on Array's length so i'll accept it (k1) ok ok so i got it as (k1) what will I believe as (F2) I cannot accept (F2) as (k), i will accept it as (k2n) Because this loop is running (n) times, let's assume (n) of the length, it is running (n) times look here so you can also write the length here Because I have written the name of the variable here a little longer, that's why I am not writing the length. The length which will be exactly that is going to be the variable input, call this function then (F2) as (k2n) and (F3) as (k3n) ok so i have already told you guys here Now here I have used (i and i) I'm free to use it I have done it here (i) and I can use it again in the second loop. and (j) can also use so don't get confused by that So now if I find a total time complexity That is, if I T(n) come out, then what will it be? T(n) will be done as T(n)=F1+F2+F3 ok it will be happen and (F1+F2+F3) will become (k1+k2n+k3n) And what I will do here is that I already told you that you can drop the non-dominant term so i will drop it And I'll go on with only this And now I will not write equal here because I have dropped non-dominant term for this And i will write here (k2+k3)n what can i write to and (k2+k3) (k2+k3), I can write the second constant and I can write as (k4n) So that's why this algorithm is O(n) ok so O(n) will run in time, where (n) is the length Since the length is given in the question, then I will report it by doing O(length) Wherever I have to answer, I will say O(length) Because the algorithm it is talking in terms of length over here you see it is talking in terms of length This is going to be a length variable, this (func1) function I hope you guys understand it So the answer is O(length), Okay. Coming to the next question By the way, I have given this program1.c to you, so you can watch it by running For different inputs you can see by running Or if you want to implement it in any other programming language Feel free to do that Feel free to do as well you can do that too, ok So guys here let's move on to the second question What is this, Find the, I have written fine here, let me correct it I wrote fine above also, find this man, this is find Never mind, these small mistakes are made Find the time complexity of the Func function in the program from program2.c as follows So look at this program, I have also made it here by doing program2.c. So you guys can also see by opening this program2.c. Otherwise, you don't want to see this program, even if I have written it here, then you should not have any such problem. I have this program inside one note I have shared this doc. with you people, you can take it from the description Look here what is it written, what is this happening First of all I will do, I will not write quickly (k1) here Let's write for another problem (k1) here Because you know I wrote (k1) for another problem, I know (k1) to be eliminated but still I wrote (k1) Now look inside for is a for When there is a for inside a for, and how many times to iterate (n)! it is going to [0,n] i.e. this loop will run, [0,n] ok, and it will run from [0,n] else if it's going to be [0.n] and it's also going to be [0,n] i.e. for 0, (n) times it will run OK, so this will run 0 for (n) times, then 1 for (n) times then it will again 2 for (n) times And so how long will it go on, it will run (n-1) for (n) times So here I do (n-1)n Here I put (+) and here if I assume its time complexity, (k2) that it takes (k2) time So here will come nk2, nk2, nk2, nk2, and out of all I can (k2) take the common ok so you understand what i'm saying Here I can take the common (k2) So look at me here, if I do it by putting arrow that is the solution to this problem. So (n) how many times it is coming, (n) it is coming in all So (n) can be taken out, so I can come out (nk2) after that i will get (1+1+1+1+1), how many times will this (1+1+1+1+1) go here It will go, if you look carefully above it is written (n) times So what will happen if I write 1 for (n) times as (1+1+1+1+1) So surely it will be (n), what will happen, it will be (n) so this will be (k2n²) So here I write this (k2n²) so it is done O(n²) So anytime you see the double for loop, and it's going to [0,n], [0,n] And there is some constant work going on inside it so it means it is O(n²) OK, so we've got to look at problem no.1. We understood it because it was O(n) And there was a very simple problem, problem no.2 also But this is a very basic problem of big O We are going to see a problem here that will challenge you. And I'm telling this is a bit challenging problem ok i am already telling this i am announcing this That's why you guys don't think that if it didn't happen to you, that it didn't happen to you, we are useless
don't think so I have not given this to you people to down your confidence Rather what I have done here just to encourage you a little that we can solve all kinds of problems here This concept applies everywhere Consider the recursive algorithm above, Should have written below not above, but never mind, I'll make it correct, I do it below where the random (int n) spends one unit of time to return a random integer, okay So here's a random function that takes one unit of time which is evenly distributed within the range [0,n] I have written 2 times [0, n] I typed it very quickly, I have to correct everything If the average processing time is T(n), What is the value of T(6)? So you have to find the expression of t(no) here, how long is it taking? that this is our function how long did it take It just has to come out, T(n) has passed, so T(6) will also found So what's the question here, the question is you find T(6) so T(6) is a small number If I directly solve for T(6) So maybe my work will be done here Okay! But what will happen, what will people do that try to derive the expression of T(n), which is possible I'm not saying it's impossible But according to me (6) is a pretty small number and you guys solve the problem directly, solve T(6) only then it will be good. So what shall I do here, I will try to solve the problem directly for T(6) only. And if this is a simple problem, then the expression of T(n) can also come out So here let's see what is happening in this function. First of all (int i;) I will call it (k1), that this thing is doing some constant work. Here if there is (n≤ 0), then it is getting return and after that this one below won't work if it is (n≤ 0) But what is happening here is that this recursive is calling a random function Which is taking one unit of time So what shall I do, I will write this as 1, okay and i would say it is taking one unit of time And the rest is written in it that if it is taking one unit of time So we can assure the rest of that is taking negligible time So I'll zero it here (0) And you know why I changed (k1) to 0 I set (k1) to 0 because it is written here that it is taking random one unit of time. and it would have been fair If I had written here that the calls which are other than random are not taking much time, okay. If I had written this then it would have become more fair. So let me add to this that the rest of the calls are not taking much time. So here you guys see how many times random calls will happen this is the question So if it is taking random one unit of time you have to tell that if the average processing time is T(n) then what will be the value of T(6) So I have to tell you how many times random calls will happen For (T=6) So over here now look what I'm doing, and I'll tell you what Random is doing here I should also have written what Random is doing here A little question is incomplete but I will complete it But now let me tell you what the question is I just complete it What will Random do if you write your random as 6? So what will it do, it will give you the middle of [0,6] So look here I have written return a random integer which is evenly distributed within the range [0,n] So it is any number in the middle of [0,6]. will give to you by written, okay. i.e. is just random, anything between [0,6] you will get by written, okay. So I do one thing, I change the color here And I do in color change, I do in red color Because what if I do it in red color, then I can do it in purple So you will know the difference between ques.1 and ques. 2. that these two are the solution of different question now look what i have done here This function is written so I just want to find what this T(6) is doing If T(6) I wrote here, Now I'll do it with recursion, T(6) is recursively calling itself For T(i) and T(N-1-i) So when T(6) will call, pay attention to what I'm doing here T(6) will call when over here, then it will be 0 times over here So once it will call Random because it is not (6≤ 0) so it will go to else, it will not go into if Watching carefully you guys, won't go to (if) it will go to (else) ok so i found out that he is going to (else) for (T=6) And one unit of work is also doing that So I will add here that this one unit of work is doing So here I will write 1 in this way Along with one unit of work he is calling his 2 child units of function and what is that, T(i) and (n-1-i) But here do you guys see one thing that (i) it is random, see here that (i) is random which can be anything between [0,n-1] i.e. in this case it can be anything between [0,5] So what do i take the value of it. now because here they have given that it is random So I can take anything, it means that whatever it is, the answer will be same. The answer will be same What did I say, I did it because the question itself is something like this Now here I will also tell you why the answer will come same But now let us assume here that I will take any value of (i). The number of calls that will be there, whatever the calls will be of T, the number of calls that will come in the same So here what we will do now, suppose I have made the value of (i) here 0 suppose it became 0 So if I make the value of (i) 0, then this function will become 0 So this will be T(0), ok and if you guys look over here T(0) is something that doesn't work Because it will return here, it will not come at random This call for (n=0) ,0 will work So here I will write 0 by putting an arrow on it, that means I do not want to add anything in T(0) and at the same time it will call T(5) Okay. After that I will break it into T(0) and T(4) Okay. into T(0) or T(4) After that I will break it into T(0) and T(3) After that I will break it into T(0) and T(2), okay that I will break it into T(0) and T(2) Similarly I will break it into T(0) and T(1) I will break it into T(0) and T(0) which means it's nothing Now these T(0), T(0) calls are coming, they are taking zero units of time. But it took my, one unit of time it took my, one unit of time it took my, one unit of time it took one unit of time and how much is it How long did it take 1,2,3,4,5,6 This means 6 times, here will be a random call So the answer will come 6 Okay! Now you will say that you have assumed one thing here that the value of (i) is always 0. but the value of (i) can be randomly anything between [0,5] So will the algorithm not depend on it? Look what is happening here that what it is doing child processes is giving, giving, giving continues to produce, until it breaks and almost ends Because the child process it is giving is calling the recursively function, it is doing a smaller than itself T(6) is not doing T(6), T(6), T(5), T(0) is doing If I do T(1), T(4) also here You guys try and see what will happen even then it will keep breaking, it will keep breaking till it becomes T(0), T(0) This will continue until there are all leaf nodes everywhere. And in that case also you will get 1,2,3,4,5,6 calls I have written a function of this, I have made a program for it, program3.c infact it's program4.c or it is program2.c or program4.c yes there is program4.c So I have implemented random over here And what I have done here is that (this) is written, (this) means whenever there is a random call then this printf will also be run So the number of times (this) printed means that the number of calls will be same So, if I run this, then you guys will see that (this) will be printed 6 times. Okay, So 1,2,3,4,5,6 If I run back then 1,2,3,4,5,6 Calling 6 times (this) So here is what is random, which is giving the value random is giving that randomly between [0,n] So it is not necessary that you verify this mathematically. But since this question has been asked, so you can take anything randomly. If your interviewer says as if after I have taken randomly here then will not depend on it If you are not sure then you can tell your interviewer that I am not sure whether it will happen or not. But because I told myself that I can take anything randomly, so I took anything randomly. Whenever you give interview, a coding interview especially So you don't always have to be right there you be so honest Along with others, show him something, because if he is asking you a question and you are blank, he will not know what do you know. But if you're approaching him in some way If you're approaching him like this, you're making a recursion tree So he will know that yes man you know all these things you have clear concept of big O You know how many times random calls are happening here, that have to count. The function given here is that the function is taking one unit of time. If you understand all this on your own, then all these things matter to you. Okay. This question was a bit tricky and I had to take this tricky question If you don't understand it, I would say look back So what have you done here, I have broken it down only I've broken it down when it's run for (6) You can proof this by breaking it for (n) It can be proved that whatever the value is at random, it will not depend on what your (i) value is. unless it bumps [0,n-1] as long as it's inside [0,n-1] sorry As long as (i) is on [0,n-1], it will not matter The number of calls will remain the same (6) I have shown here by practically running that this random which is generating the numbers randomly I have run it even then (6) is coming, and again and again (6) will come, okay You can also check it by putting it in the loop whether (6) is coming or not, okay. So back to one note And look here what the fourth problem is saying, and the fourth problem is very simple Which of the following are equivalent to O(N)? Why? Which of the following is equivalent to O(N) and why?
let's look at the first So it is O(N + P) and I know where (P < N/9) i.e. it's a non-dominant term, okay What is (P), non-dominant term, here it is clearly written in the question I do one thing, which is my pen, I change it a little. i do it. So look it's non-dominant term as you see Need a little thin pen man Yes, it is a non-dominant term, so what can I write it, can I write it O(n) so it is O(n), okay Let's look at this (9N-k) where (k) is a constant, so I can eliminate the constant like this. So then it will be O(n) Because I will eliminate (9) also It got eliminated because of the non-dominant term, and it got eliminated because of the constant, right So this constant will become non-dominant in front of (9N) for very large (N) values and (9) is a constant with (N) so I removed It is also O(n) So it is, this it is, and see this is it This is also visible because (8log N) is a non-dominant term It won't be able to dominate in front of (N) because (log N) grow a lots of slowly (N), grows more than (log N) if I draw a graph of (log N) So it will come something like this, and (n) will come like this (log N) will come like this So for very large values, what it is (N) will always be above (log N), Okay. It is also O(N) see this (N + M²) Now here if this (M) is a constant I should have written here in brackets, where (k) is a constant Should have written like this, I didn't But I should have written here (k) is a Constant, I will add to the question here (k) is a Constant Because if you do not know what (k) is, is a constant or not like here there's (N and M) It is a O(N + M²) algorithm It cannot be written as O(N) because (M) is also an input so you cannot ignore it. So (C) is O(N), and (D) is not a O(N) And in the question which I have not added the details, I will also add all that. That's Doc. i will update what it is So that when you solve the question without looking at the question, then you will not have a problem. Okay Now let's see here what is the fifth question So we have solved 1,2,3,4 questions very good Ok so this also got solved, I put a tick on it too. Now, here I see that The following simple code sums the values of all the nodes in a balanced binary search tree Now here I will tell you a little bit about the search tree, I will not tell much, I will tell a little, okay And whatever is there, your work will be done I will tell you further, I will tell you very well do not take tension, you guys But for now just for this question What is a Binary Search Tree, understand it as such that It's a node, and it's something like this, so I'll zoom in a little bit So it goes something like this, we have a node, we have a node here too and back inside it has a pointer which is pointing to another node And it's pointing to 2-2 nodes, okay So if you read about Balanced Binary Search Tree then Well, I will tell you further, but if you do not know, then understand that there is a structure here, which has 2 pointers. Which are pointing to different types of nodes, like this Now look what this algorithm is doing Because this question is very straight forward, here you will not have to go into the details, this question is such that it will be solved on seeing it. I have taken an example like this So you guys look at this So what is it doing, whatever it is doing, because it is written here that it is sum all the values. Sums the value of all the nodes It itself showed that it is doing sum : Value of all the nodes Question is speaking one thing by itself, then the question will never contradict itself. So the question itself told that it is counting the value of all the nodes. And it's saying what's its runtime If I assume that which is (n), I will write here that (N) is the number of nodes. Number of nodes So what will be its run time, you tell me by commenting, I want you to tell by setting the time system What is it doing, first of all it will sum of it Then what is it saying that sum him, call him for this Then it is saying do a sum for it, if this node is null, that is, there are no other nodes below it. So what is it doing, returning 0 And here the value of this node which is, will be summed up to be the backtrack. So basically this is a recursion, Okay But here I want to realize one thing to you guys. How much this code is working, this code is almost working same for every node OK, so for every node So the more nodes there are, it will be big O. A little bit I have told you directly here It will O(N) happen, I'm telling you but over here if you try to figure it out over here what it's doing It's calling this recursive function and it's sum for all nodes which is doing the work for it, is doing the same work for it. is doing the same work for it. And finally nothing is working for the nodes which are below, but when it will grow the tree, which is (N), number of nodes depend on its run time. So this I have directly told you here But again we will talk about Balanced Binary Search Tree And I solved this problem very quickly. So here you guys just keep in mind that never solve this kind of problem in a hurry. Now if you don't know the Balanced Binary Search Tree So maybe you can say this directly to the interviewer, that I don't know So this would be a very big red flag if you say that I don't know about Balanced Binary Search Tree. Then obviously he prefers to the person, to whom all these things come It's very simple: I will tell you next But for now let's move on to the next question: And on this question you can come back and come back and revisit on it and you can see it Because the query it used to depend on the Balanced Binary Search Tree But I told you with an idea that it is working same for every node so that's why it is a O(N) Because when it grows, this is the tree when it grows, the input size when it grows So it is working almost same for all the nodes, you can see here Because if node becomes null, node itself becomes null This node is not null right now, it is pointing to null ok so it points to null If you haven't read the binary search tree By the way, it's not fair that I will tell you all these things right now. i will tell you ahead But if both of these are pointing to null So what does it mean, it is doing the same work for this doing the same thing for the ones below: this if you look at it carefully So it is doing this for the below ones, and for them it is doing return (0) So it is working for all the nodes at the same the number of nodes it has will be its run time. So if you write the run time, then you can do k(n), T(n) and after that you can do O(N) So i think this is very clear, Your interviewer can sometimes give you a hint If you do not know Balanced Binary Search Tree, then he can tell you what is Balanced Binary Search Tree. And from there he will tell you that now you take the problem ahead. So i hope you guys have understood the problem 5 So if it seems a bit strange, then am telling you to revisit it. after reading the Balanced Binary Search Tree, Okay Now look here what it is doing It's a little tricky, but it's not that tricky, but it's quite Look, what this code is doing, testing this code, whether a this number is prime or not
If you have already seen this code Then you guys can trust on this code here So it is saying itself: it is testing whether a given number is prime and not Okay! So it said itself in the question that I am checking whether this number is prime or not: Okay So over here if I do and analyze this code and then I will not consider it because it is a constant. ok, so this checking which will be done in: (k1) time Assume that as (k1) I will not write again and again in my time But let me analyze this: because it's coming here (N) I have to analyze that much part Now let me see how many times this loop will run just to see: and it will be (k2) And at first I will write T(n), (k1 + k2(N2)) as as many times as this loop runs, let's see how many times this loop will run So this loop is running, it is starting with (2) :loop Okay and going until it becomes i²=(n-1) When i²=(n-1), then its last executable will be Let me see: with what value of (i) it will work with So this will work for i=2, will work for i=3 And how long will it last, what will be its final run, what will be the last run, what will be the value of final (i) It will be (√n) Look when the value of (i) is less than (√n) So any number which is less than (√n), will run till So let's assume that this is going on till (√n) It is not necessary that it should last till (√n) Since the value of (N) cannot be (N) perfect square But let me suppose that (N) is a perfect square Otherwise this (√n) of which will be our greatest integer It will go till there, Okay I don't want to get a bit complicated here, so you can assume it will last (√n) so the value of (i) is running for 2, is running for 3, so it will last for till (√n) So it will go approximately up to, (√n-1) this loop will run approximately (√n-1) If I use a rough idea so I can take it (√n) These are all constants, whatever will be behind it So if I solve this problem quickly then, I would say it will last till (√n) It almost always starts with (2), until (i) become (√n) or less than (√n) It's going up there, okay So it will last till almost (√n), so I can call it O(√n) So here you guys will have to apply approximation sometimes Because it can have constants in front, behind, (+), (-) but (√n) which will be dominant term when the value of (n) is very large And those constants won't stand before it at all So that's why it will happen O(√n) Ok, so we have solved the problem of (6) also. Now this is the seventh problem, it is very interesting, you guys see here Whoever I have called this prime should have given a number too. As if I am giving (18) to this, well I have made a mistake here: I will correct it I should have given an number inside this prime What is the time complexity of the following code snippet It has named this function: isPrime Okay But when you look at it carefully, you will know that it is not checking for prime number, it is doing something else. But your interviewer may ask you questions like this Because he will expect from you that you speak out of fear at once O(√n) Because you already have this problem, you have solved this problem: Because he wants you to get nervous, hustle, lurk O(√n) You speak quickly, and he will say wrong because in this: there is no (n) So what is it here that it is not fully dependent on (n) Because (n) is taking in input but (n) is not coming down anywhere. So this means it will be a constant, I can assume that (k1) Because no matter how big the value of (n) is, it is running only 10,000 times, so i can consider its time as constant And i can write T(n) as (k1), or i can write as O(1), i.e. running in a constant time Now again (7) questions which: what we do of big O And i hope this question will help you guys a lot I want you to raise some questions from anywhere of big O by searching the internet, Or if you are following any textbook etc. then you can pick it up from there, nowadays there is no shortage of questions. solve them by lifting them These (7) questions will help you a lot I will do one more thing, will make videos of more problems in future But according to me, we have time: to move on We take this concept forward the course of Data Structure and Algorithm: Because if I solve a lot of questions in big O, then I do not want to spend a lot of time in it. I told you guys that you can solve any problem of big O or any. And to solve some of big O's problems Whatever you guys were talking about, like the binary search tree We will talk about stack, queue etc. All of them can use to him, all those things can come mixed in it. And as all those things mix, we'll keep talking about big O again and again. So this is not the end of this topic This is not the end of time complexity. we will talk more about it But, i think for now this is enough for practice If you want to do more then it is a very good thing, but according to me right now, practice is enough: Next we will take more practice We will continue to practice the questions. so so hope you guys liked this video One thing I want to tell from my heart to all of you please share this playlist. I am doing a lot of hard work for you guys, I have made notes for you guys. You will also find the notes of this chapter in the description. And this is the sheet you will also get it I will give it to you by putting it I hope that you guys like these all things And you guys are enjoying this course That's all for now in this video Thankyou so much guys who watching this video And i will see you next time.