- 2 days ago
Transcript
00:00Next we have a very big question. This is our nested loop 3.
00:03What is it? We assume that there is a constant k
00:07which is very small from n.
00:12What is the outer loop? I is equal to 0.
00:15I is less than n. I am running the outer loop.
00:19Every time i is equal to i plus k.
00:22What do we have seen? I is equal to i plus k.
00:28Every time i is equal to i plus 1.
00:30This time i is equal to i plus k.
00:33What is the inner loop?
00:34In the inner loop, j is equal to i plus 1.
00:37Where do we go to the inner loop?
00:39We go to constant k.
00:40Every time we do j plus plus.
00:42Every time in the loop,
00:44p is equal to constant walk.
00:46Now, I will take an example of it.
00:50What is an example?
00:51I assume that the value of n is 50.
00:54and the value of k is 5.
00:58This is my example.
00:59We will build a little understanding.
01:02What can I say?
01:03I am telling my java outer loop.
01:05It is going to go to 0 to 50.
01:08If I am in a line.
01:11If i is equal to 0.
01:13If i is equal to 0,
01:15it is equal to 49.
01:17What can i call total length?
01:19It is equal to 50.
01:20I am trying to go to 0 to 50.
01:23What is the value of i?
01:24This time i is taking jumps.
01:25The jump is greater than 1.
01:28If i is equal to 1,
01:31If i is equal to 0,
01:32When i is equal to 0,
01:33then 1 will be equal to 0
01:342 will be equal to 3,
01:363 will be equal to 4.
01:37But now i is taking jumps.
01:38How many jumps are you?
01:39It is taking jumps by k.
01:40So here at 0,
01:42if it is 5 plus,
01:43then 5 will be equal to 10.
01:44Here's 10,
01:4515 will be equal to 20.
01:46We will take jumps by 50.
01:49What is the difference?
01:50What is the driving loop of outer loop?
01:51We are trying to go to 0 by 50.
01:54The way is the driving loops of 5.
01:56And what is the length of inner loop?
01:57The inner loop starts from i plus 1 and goes to k.
02:02So what can I say?
02:03When i value is 0, what will my inner loop start?
02:06It will start from 1.
02:08It will start from here and where will it go?
02:105.
02:11So every time my inner loop tries to cover this distance.
02:17So what happens?
02:18If the outer loop jumps,
02:20the inner loop tries to cover this distance.
02:26The inner loop starts from i plus 1 and goes to k.
02:30If i don't know that i plus 1 is 0,
02:34then every time my inner loop goes to k.
02:38Every time my inner loop goes to k.
02:39If any loop goes to k,
02:42how many steps are going to k?
02:44I can say that every time my inner loop goes to k,
02:49what am I doing?
02:50I'm trying to cover this distance.
02:51I'm trying to cover this distance.
02:52If i went to i then I jumped here.
02:56I went to k and then I got to j.
03:00Then I Para by I jumped here.
03:01Then k after k steps,
03:04check here.
03:05Then k after k steps,
03:06check here.
03:07So the inner loop is J is covering the distance.
03:10I am covering the distance and I am taking the big jumps.
03:12So when we look at the final output,
03:14we will know how much I did the work.
03:17The loop outside has jumped.
03:20The loop outside has jumped.
03:22N divided by K.
03:24How did it do?
03:28Because it had to go from 0 to N.
03:30It took K jumps.
03:34If I have to go from 0 to 10.
03:36And what do I do every time?
03:37I take a jump of 5.
03:38So how many jumps will I reach?
03:401 jump, 2 jumps.
03:42So what is the value?
03:43It will be 10 divided by 5.
03:45That means my N divided by K.
03:47Which is equal to 2.
03:49If I have to go from 0 to 15.
03:50And I can take a jump of 5.
03:52So 1, 2, 3 jumps.
03:54That means 15 divided by 5.
03:56Which is N divided by K is equal to 3.
03:58So with the same logic.
03:59If I have to go from 0 to N.
04:01And I can take K jumps.
04:02So how many jumps will immersion and operations will be finishing it.
04:05Which is to be doing N by K.
04:06What is the load working inside?
04:08The load JT Do the whole-ends for K's.
04:09What is the load gettingations from 0 to K-II?
04:12So every time, every time, the load JT nights is working冗uted.
04:15So the load JT As done is multiplied by under.
04:19Which time it works?
04:21Which time it works at N by K?
04:23This is N by K.
04:24Then it's done польз with N by K.
04:26variance again and reverse the new mode.
04:29This is the other- fazendo and the other.
04:30So this is multitude of JT Kingdom.
04:31What value will I give?
04:33This will give me big of n by k and multiplied by k.
04:36And here I can also write multiplied by p.
04:39Because what is the work of p every time in the loop?
04:42Now what do I do?
04:43This will cut from this k.
04:45Big of n, p will come to my work.
04:47And because p, what is my constant?
04:50We ignore constant.
04:51So big of n will come to my time complexity.
04:54This is a very important question.
04:55Why is it very important?
04:56This is important because here I think that
04:59there are two loops.
05:00And these are nested loops.
05:02So the first time we see this question,
05:04I think that the work of n2 is doing.
05:05But how much work here is linear?
05:08Why is it linear?
05:09Because I always take n to 0.
05:13But I take the outside loops.
05:15And the inside loops cover this little distance.
05:18I told you about k to 0.
05:20If we come to the original,
05:23ij will start from i plus 1.
05:25So what can I say?
05:26i plus 1 is always bigger than 0.
05:28So if it is 1, 2, 3, and then k.
05:33So it will always be less than k.
05:36So what was the worst case?
05:37The worst case was to go to 0 from k.
05:39After that, you go to 1 from k.
05:414 from k.
05:435 from k.
05:44This will always be less.
05:47It was the maximum of k.
05:49And according to that,
05:50we have removed time complexity.
05:51Which is big of n.
05:53So the entire loop of time complexity
05:55that is big of n.
05:56And we have analyzed it in a very important way.
06:00We have seen jumps.
06:01How is the outside loop update?
06:03How is the inside loop update?
06:04How is the inside loop update?
06:04where is can you go to the outside.
06:05Okay, so the outside Dorothy.