In this Video, we are going to learn about 2 important concepts i.e. Time Complexity & Space Complexity. 
Its going to be a short n Interesting one, Do watch it full.

There is a lot to learn, Keep in mind “ Mnn boot karega k chor yrr apne se nahi yoga ya maza nahi para, Just ask 1 question “ Why I started ? “

Coding Ninjas: https://bit.ly/3cfdKTe 
Visit Codestudio: https://bit.ly/3lrUGWN

Discord Server Link:  https://discord.gg/feSQvVXMrd 
Course Flow: https://whimsical.com/dsa-4-placement-by-love-babbar-C7JX2fJ8hprv9ivEHkArjD@2Ux7TurymNF9zkFahVLk 
Homework:  Added in Video already 


Notes Link: https://drive.google.com/file/d/1fNYvJ_FlJr6E5X8IREKUPfRX1-Vu27pF/view?usp=sharing

Code Links: https://github.com/loveBabbar/CodeHelp-DSA-Busted-Series 


Telegram Group Link: Love Babbar CODE HELP
https://telegram.me/lovebabbercodehelp

Do provide you feedback in the comments, we are going to make it best collectively.

Connect with me here: 

Instagram: https://www.instagram.com/lovebabbar1/ 
Twitter: https://twitter.com/lovebabbar3


Intro Sequence: We have bought all the required Licenses of the Audio, Video & Animation used.

Timestamps:
 
00:00 - Introduction
01:19 - What is Time Complexity ?
02:36 - Why Time Complexity ?
03:50 - Promotion
04:53 - Example
06:12 - Complexity Notations
08:25 - Big O Notation
11:10 - Solving for Time Complexity [Problems]
20:34 - How to Avoid TLE ?
23:46 - Space Complexity 
24:06 - Solving for Space Complexity [Problems]

#DSABusted #LoveBabbar

This is Love Babbar and welcome to the channel Code Help.

This is the lecture number 11 of our DNS series.

Here we are going to talk about a very important topic.

Which will be asked after every question of every interview.

Its name is Time Complexity, Space Complexity.

We are going to discuss about the complexities.

What is time complexity why it is there what is the reason how you can find out time complexity about TLE, Time limit exceeded error which we saw in last video.

We are going to discuss about all those things.

So, we will not study time complexity and space complexity we will study the knowledge we have acquired and we will understand time complexity and space complexity I had planned to take a dedicated lecture after the recursion but now I am going to need some time so I am going to give you some knowledge on time and space complexity A dedicated session, a dedicated lecture will be coming after this recording So, in this video we are going to talk about time complexity and space complexity We have understood this much only, very good

go first thing that comes to our mind is what is time complexity what is time complexity let's understand this we said it is the amount of time taken by an algorithm to run as a function of length of the input.

So, we are showing the time taken by an algorithm to run by making a function of the length of the input.

That how much time it takes, I am going to know about it and in which form I will get to know as a function of length of input Done?

So this is called time complexity I wrote an algorithm which tells me whether a particular number is prime or not Now how can I say whether algorithm is good or bad slow or fast How will I get to know If I can tell the time complexity of the algorithm is O of n, O of n square, O of n factorial Based on that I can tell if this particular algorithm is good or bad Done?

We understood that what is time-perfected?

It is the amount of time taken by the algorithm to run as a function of length of the input We understood that this is nothing but time The algorithm is telling us how much time it is running We have understood this thing Why?

See, if I speak from your point of view from a logical point of view, I mean if I talk practically then after every question in the interview your interviewer will ask, what is the time complexity of the code you have written?

What is the space complexity of this code?

Can I find a better solution for this code?

Then you will give an optimized solution Then you will ask about the time complexity Can I optimize it more?

Time complexity and space complexity is something which you will be asked again and again Guarantee of this There will be no interview where you will not be asked about time complexity or about optimized solution so that is a good reason but still if we talk about good point of view so first thing is for making better programs you should know what program is good and what is bad what program is considered fast and what is considered slow with this you will know the truth of time complexity so you should know comparison of algorithms you have written 2 algorithms which 1 is better?

Suppose I have written 2 algorithms so what I have done is this is my algorithm A

so before moving ahead in the video let's talk about coding ninjas to make this free DSA course reach you From content quality, content expertise to video sponsorship.

Coding Ninjas has supported a major chunk of the free DSA course in getting you to this point.

Coding Ninjas is 1 of the largest coding education platforms.

largest coding education platform where you can take many types of courses if you are interested in

paid courses if you want to do development, machine learning, android web development, course subject OS, DBMS I can do

DSA, Java, Python in any language, then you can take paid courses The most beautiful thing that people praise about

Coding Ninjas is that one-on-one doubt resolving support is available here.

If you have any doubt, it will be resolved in 1-2 hours.

The courses that are made are very well structured.

put in hard work, you will definitely get the result.

If we talk about language, Hindi and English are available in both.

While solving the questions, you will get hints in the videos.

So if you want to buy any period course, then you are smart.

Thank you and this is my algorithm B now I know that algorithm A has more processing I do more processing in this This is high processing algorithm Both do the same work But B is low processing algorithm I know that this 1 is fast And this 1 is slow But how can I tell?

I can't tell by intuition that this is fast and this is slow I have to

a data point If we assume that we run this algorithm on a slow machine and run this slow algorithm on a fast machine and now the output we are getting we are thinking that this is fast algorithm and this is slow algorithm but we are getting slow or fast performance because of machine so we can't tell based on that whether particular algorithm is fast or slow so we have 1 thing based on which we will tell that is time complexity I will not tell based on machine It's not like I have given time there, when it started and when it ended I have told you on the basis of time So time complexity is your matrix through which you can tell that particular algorithm is fast or slow You can compare which is good and which is bad ok very good what will I show like I can show distance in meter, centimeter, kilometer there are many units right I show in those units that this is like this, this is like this in the same way to show time complexity I have big O notation I have theta notation I have omega notation I have different types of notation Which 1 I am going to use?

You must have heard many times that time complexity is big of n, big of n square, big of log n.

It means that this particular ABCD algorithm will take maximum time.

Worst case complexity is this it will not take more time ok for example, I will say I have a Ferrari and to reach 0 to 100 it takes 6 seconds it takes 6 seconds not more than that I want to give you some example I have a banana, I want to eat it I will take maximum 5 seconds to finish the banana I will not take more than that I have an algorithm like that If I want to show its complexity in upper bound I will tell its complexity in big O Big O of n, big O of n square etc.

If I want to show the lowest bound, then it will take 3 seconds to reach from 0 to 100 we are not talking about Atom X we are not talking about upper bound, we are talking about lower bound so we will talk about Omega ok and if we are talking about average case, we will talk about Theta we will study about this in depth later now our focus is on Big O notation, which is practical the things which are asked in the interview, which will be discussed in the paper through which you will be placed.

I will not talk about it much otherwise I will waste your time.

So what I got to know is that big O notation is a notation which explains me the worst case that this is the upper bound and time will not be more than this It will be less than this but not more than this.

Whenever your complexity is constant, it will be in fixed time.

We will discuss what is constant time in the future.

Suppose I run a for loop from i0 to i10 and here I print hello so this is constant why?

10 which is fixed there is no variable in this it is fixed that it will print hello 11

It is fixed that it will print hello 11 times.

So the complexity of this program will be constant.

I will show it by writing O of 1 If I change this value to 0 to n Now n depends on the input value of the loop So I will show it as O of n if it is complex log n like binary search example we will read it later there we call it logarithmic time n square is done suppose I run 2 loops, first loop from 1 to n, then run another loop from nested to 1 to n.

This is an example of off n square, which we call quadratic time.

Suppose I talked about cubic time, n cube, so what I did, I run another loop in these 2 loops to n.

So, I run 3 loops and this becomes n square.

These are some examples of complexities there are such complexities you will see some words like o1, on, n2, n3, log n you will not get scared ok, lets move ahead I said that if you want to see the notation of graphs, then you have to understand how the graph is going to be.

If I talk about constant time, then the graph is going to be like this.

If I talk about linear, then the graph is going to be like this.

All these things are the same as you have already studied in your class.

This is how your quadratic graph is going to be.

This is how your logarithmic graph is going to be.

And I said that the complexity in this table O1 log n, O1 n log n, n square, n cube 2 power n factorial the complexity is increasing while going up this is the least complexity in this table this is the least and this is the highest in this table ok, so if someone asks you that in n square and n log n which 1 is more complex you will say n square is more complex than n log n so you can put this in front of you so that you can get a better idea of which is bigger and which is smaller ok, lets move ahead now we are going to give you some functions time complexity is the representation of this particular function we know that big O notation is an upper bound notation so when upper bound is shown it is explaining that you will not go above it, you will stay below it so we give this function to lower degree like here degree is 2 and here degree is 1, we always ignore lower degree so in this case, what will be the complexity?

O of n square we ignore the constant which is 1, 2, 3 so what you have understood so far?

Ignore lower degree and ignore constants very good, so your answer is O of n square I went to this game, I ignored constants and this is lower degree and this is higher degree, so what is the answer?

Okay, I understood this thing we know that we saw in table that this is considered as a complexity and this is considered as a more complex complex.

Whenever you have a plus sign, you have to take the option.

So, we will take the most complex operation in these 3 In this, degree is 0, 2, 3 We have called it simple, O of n cube Done We won't see if it counts 1, 2, 3 We don't care about 3, 2, 5 Here, there is already a number Number is fixed, there is No variable I can write it as constant time In this case I don't care about 300 I have written n3 above and my answer is O of n Here I know n2 is bigger than log n and I don't need to see 5, so answer is of n2 Here I know I don't need to see 4, so answer is linear time of n Here I see that I need to see 4, so I need to see number of n, so answer is of n linear time so you have seen some examples from where you can understand that if I have this kind of function in front of me then how will I find its complexity I have understood this, you are finding it very easy you have enjoyed it, ok I am understanding this thing now done?

Ok, so the program which we have written till now how to find the time complexity in that ok I will show you some examples we will try to find the complexity of those examples ok first of all we will go to print array let's understand this thing we went and we saw what is happening in print array there is a for loop which is going from 0 to n and printing something in n.

So, what you can see in time calculator from 0 to n bar, there will be total n iteration.

the input So, you can see that the time column is

to n bar, which means there is an iteration of n And

then we swapped n by 2 so we swapped n by 2 So my complexity is O of n by 2.

In linear search, We had an array of n length And we had a key, we were checking it everywhere We will do n bar comparison We did n comparison We ran for loop from 0 to n So, how much complexity will be there?

It will be of n we have understood this ok, so we have understood this much now I have taken some pics from the interview bits we are going to see them once from there we will see the time complexity from there so what is the first question this 1 in this they have said a0 b0 first loop is from 0 to n so what is the time complexity of the first loop?

When there is another loop outside, you will apply a plus sign.

And when there is a nested loop, you will apply a multiply sign.

For example, there is a for loop like this.

And after that, we have applied another for loop.

So, what we have done is, we will add the complexity.

Let's say, its complexity of O of n and O of m so we will add O of n plus m but if we add 4 loop and add another 4 loop inside it so here the game is different suppose if n bar runs then m bar runs so our complexity is n multiply m in nested case

if you have different loops then you have to add them so in this case if we see there are different loops, first loop is n bar and second loop is M bar so what is our complexity?

O of n plus M this is our time complexity ok, now we move ahead we will discuss space later ok, this is our second question in second question, what is shown?

First loop is n bar and there is another loop in it which is running n bar again.

They ran a for loop from 0 to n and then ran another for loop from 0 to n and then closed it.

I know that this is n bar so what is this?

O of n multiply n, means O of n square we have got a good complexity.

It is not yet over, there is another loop below that is again n bar 0 to n what is the complexity of this?

O of n if this was different from this, then this will be plus O of n square plus O of n we know that this degree is more, so what is our answer?

O of n square, this is our time complexity ok, let's move ahead, I have taken out another question I have opened this question, what is happening in this question?

There is a for loop which is running from 0 to n Then there is another for loop which is running from n to I and you have closed it I can see how many times it is running, n times complexity in big O notation is very easy you don't have to work hard, you just have to pick up the worst case now in worst case how many times will the inner loop run in worst case inner loop will run, I will be 0 and this is n so this loop will run n times and this is nested loop so it will be multiplied O of n square simple thing you just have to pick worst case not like this pick a simple worst case and give your answer simple thing so we have done 3 questions and now we will try our own questions and see what will be the complexity of this like we will take out the max and minimum so what we did in this We had an array with some elements 1, 2, 3, 4, 5, 6, 7, 8, 9, 15, 16 We had to find out the maximum and minimum number of the array We initialized the max and min with int and min we have to find maximum number and minimum number we initialized maximum with int min and then we compared with everyone and updated the chain we traversed the whole chain we looped the chain from 0 to n complexity of n is over what is n here?

Length of array good we have understood some things, lets try to go further lets see the isprime function it ran from I to n and it ran 1 loop, then again it ran from 2 to n, What does it mean?

I ran it n-2 times You put n-2 in O So your answer is O of n Things are very easy for you you just have to calculate the complexity you are counting from 1 to n it's fun what you are trying to say is whenever I run loop from 0 to n whatever I am doing inside your complexity will be O of n no I didn't say that whatever you are doing inside if it is in fixed complexity then your O of n will be there.

But if you have made a function call inside, let's say you have made a function call inside, you have made a function call, you have done anything, I have passed an array or n or whatever I have done and inside this function you have added some for loop so our complexity will change so when I say for loop is running from 4 to 0 so your complexity is off n it means that the processing inside is happening in constant time like here what is happening inside it is printing in constant time that's why I said it is off-end keep this in mind don't get it wrong ok let's move ahead, even, odd, all are same so according to me, you have understood a little bit that ok, I can remove the complexity I got a little bit of idea we will go to full-fledged now we will go to full fledged now we will go back and see if we skipped anything So here we will see recursive time complexity later, not now We will see it after reading the recursion In the last video we got stuck in TLE We got a time limit exceed error Your logic is taking more time and we have to work in less time So how do we know which algorithm to use in that case?

So we have a rule 10 to the power 8 operation rule It says that modern machines can execute 10 to the power 8 operations per second they have the power to execute 10 to the power 8 operations per second so based on that we can decide which complexity algorithm to put here so to save TLE we can put this study we have read in questions that we read constraints let me show you how we read constraints and it was written there that value of n lies between this and this.

For example, if I show you, you must have seen this question.

Here you read this constraint that value of n lies between 5 and 1.

Here you saw that the length of the array lies between 1 to 1000 You must have done pair sum If I go in this, you must have read that constraints are given in this way So, on the basis of these constraints, you can decide which algorithm I will apply How?

When 10 to 11 is given Who are we talking about?

The 1 which is going to come in the input On the basis of comparing that input with this Suppose you are told that your nj is between 1 and 10 to the power 6 when you have given 10 to 11 which is going to be input based on that input suppose you have said n goes from 1 to 10 to 6 you will get to know at max at max I can use O n log n algorithm I can use less than this But I can't use any algorithm above O and log n If I am asked to use 10 to the power 8 then I have to use linear time or logarithm time No 1 will work above this, all the theories will be destroyed So from here you have put a game that I have 3-4 logic in my mind But which 1 of these will pass all my tests in reality, you have this chart 10 to the power 8 operations rule you have learned this now solve this question we are solving this on leadword or any platform make sure that you are

chart is this chart valid are you getting help from this chart?

Pay attention to this when I say that the input can be less than 10 to the power 4 then it says that we can use atom x of n square.

But if you try using any of these, it will not work.

So, you will understand that this is how it works.

This way, you can avoid the time that comes in TLE ok now if I move towards your space complexity suppose I told you that space complexity there is a program in it, show me what is space complexity let's go again, we have seen 2-3 programs, how will it be in it we will not discuss more on this, we are going to do dedicated time later so, not much effort see, we have said space first, what is space complexity?

Again, like we have said about time complexity that you are making a function of the input and showing on its screen how much time your algorithm is going to take similarly, you are telling how much memory your algorithm is going to take as a function of the length of the input instead of time, it is memory so this is your space complexity if we see here in this program, what space you have taken you have made 1 variable a, 1 variable BIJ, etc when you make variables, you don't have to take tension that I have made 10 variables, 50 variables, so what should I do?

You are making variables, int a, int b, you have left space.

Space complexity is considered as O of 1 It is called constant space Done?

It comes in constant space We will call it O of 1 space Let's go ahead Again, carefully, variable is made Again O of 1 space See Again normal variable Again O of 1 Now let's go to a case where something is different I have written a program function and here I have created an array if I have created an array of 5 size in this 1, 2, 3, 4, 5 I have done some operations like o of 1 and done now I am asking you to tell me the space complexity of this you said it should be more than 1 I said why?

You made an array here I know it is a fixed size array of 5 it must be of 5 size only I will say again it is of 1 size understand this when we wrote fix here it is of 5 we said it is of fixed size it will come in constant space but if I make it like this I made a variable n then I made n as input and then I made a vector vector int v and I gave it a size n Oh my god!

Based on this variable, you have created a vector.

So, we have created a vector of length n So what is our space complexity?

We have understood this If I wrote a for loop which runs from 0 to n and then I created a vector here vector int v of n size and I wrote another for loop which is running from 0 to n everything is inside it now I will tell you what is the space complexity of this think this vector is created by this guy so this is of O of n size then this for loop will run and then it will come back on second iteration and then it will be created again by scratch then it will run again on third iteration and then it will be created again with scratch so at any particular instant of time your memory will be of n blocks so don't do this that I multiplied 2 for loops and said O of n square no, that is time complexity we have to check on space complexity vector has taken memory not for loop for loop does not take memory time of for loop is going to be consumed vector consumes space so space is consumed and we put it in space complexity you must have understood this we have created array and vector we have created this memory so I can show space complexity from here if I show you in my old program what will be the space complexity so let's try here nothing is there we have written fixed so it will be constant we can say constant space complexity we have done constant space things we have not used vector in our code we will do that also with time but we have understood how space complexity works we have not gone in depth,

Main intent is that I will teach you binary search so you will have an idea of time complexity I will teach you sorting algorithm so you will have an idea of time complexity This is what I wanted, after this lecture you have got an idea of time complexity Now if I tell you that the time complexity of this function is O of n You will say yes Go ahead Tell me more Ok I will tell you that the binary search has a complexity of O of log n You will not say yes You will not get the answer You will say yes Right the binary search is of log n so you won't be like this when you will see the word you won't get that ok right so this way we end this time complexity space complexity I hope you enjoyed it This is 1 of our short videos.

You have to write in the comment section.

I have to tell you that I have watched the whole video in 30 minutes.

If you have told me to tell you, then I will tell you in the comment section.

See all CodeHelp - by Babbar transcripts on Youtube

Lecture 11:Time & Space Complexity || How to avoid Time Limit Exceeded [TLE]