00:00Next time let's talk about this nested loop, first of all I have to analyze how many loops I have,
00:06I have two loops, this is my outer loop, this is my inner loop,
00:12I have an iterator i which is taking value from 0 to n and every time i is plus plus,
00:18that means one operation, then another operation, then third operation,
00:21then my inner loop is j, the value of j starts from i plus 1 and where is it going
00:28to n,
00:29and what happens every time, some constant work is running,
00:33so let's assume that the constant work is running, this is k is running,
00:37and the time complexity will come in nested loop, how much will it come,
00:41the time my total work is performed, now let's analyze how the total work will be,
00:46how will it come, if I take n to 3, then what can I say,
00:51first of all i will be 0, i will be 0, then j will start from 1,
00:57and where will it go, n will go to 3, then i will increase 1,
01:03this first line I have written, i will be 0,
01:06so i will initialize with 1, then j will go to n-1,
01:13and where will it get from 2 and its values,
01:15so I will linear up to .
01:17and where will it come from 2, then i will change will I value 2,
01:23and where will it become 2 and the value I will change the value,
01:26which means that i will change twoader loop,
01:38So how many loops went my loop?
01:40How many times my total work?
01:42What will I do in my total work?
01:45How many loops went i is equal to 0?
01:48This loop went 2 times.
01:50i is equal to 1, this loop went 1 times.
01:53i is equal to 2, this loop went 0 times.
01:55I went to 2, then a loop went 1 times.
01:581 went to 2, then a loop went 2 times.
02:01How many operations have performed?
02:03My operations performed, that is 2 plus 1 plus 0 is equal to 3 operations.
02:07Here I have one thing.
02:09My total work is only because of my inner loop.
02:13Outer loop is good, value is updated, updated, updated, updated.
02:17But if I add the total work in inner loop,
02:20then the operations are performed.
02:22So the nested loops, the time complexity,
02:25I will remove two ways.
02:27One is my way to see my outer loop.
02:30How many times will it go in the worst case?
02:32And then I will multiply it.
02:34My inner loop, how many times will it go in the worst case?
02:38But this is not always the right answer.
02:40For those cases, this is the easiest way to solve it.
02:44It is the easiest way to solve it and the fastest way to solve it.
02:45But it is not always the right answer to it.
02:47Because in some cases there is a little trick.
02:50Now the other way to solve it is the easiest way to solve it.
02:52I will look at the total operations.
02:55Or look at the total runs.
02:57How many times will my program run?
02:59How many times will my program run?
03:01I will remove it.
03:02So I will remove time complexity.
03:03Here I will remove a pattern about the nested loop.
03:06What is the pattern?
03:08When my i value is 0,
03:10then my program runs how many times?
03:11N-1 times.
03:12If i value is 1, then it will be N-2 times.
03:15If i value is 2, then it will be N-3 times.
03:17This is the same pattern.
03:18I have observed this pattern.
03:19If i value is N-1,
03:23how many times will my code run?
03:25The code will run 0 times.
03:27And how will my job be?
03:28My job will be adding all of them.
03:31Because the real work is performing in the inner loop.
03:33So if I add N-1,
03:36plus N-2,
03:37plus N-3,
03:39I will take it to 1 plus 0.
03:41If I calculate it,
03:43then I can say that this is my AP.
03:45How is AP?
03:460, plus 1, plus 2, plus 3,
03:48till my N-1.
03:50So I will take a formula here.
03:51What is the sum here?
03:52What is the sum here?
03:53N into N, plus 1 by 2.
03:55Here we will remove the sum from N-1,
03:58which will be N into N-1 by 2.
04:02What will happen?
04:02This will be N-2,
04:03minus N by 2.
04:05That is,
04:06how many operations,
04:07or how many operations are being performed?
04:09Big of N-2 by 2,
04:11minus N by 2.
04:12I can say that
04:14it is constantly ignored.
04:16This is ignored.
04:17This is ignored.
04:18Now,
04:18take the largest term.
04:20The largest term is ignored.
04:23What has been big of N-2?
04:26I have big of N-2.
04:26So nested loop,
04:27what is nested loop?
04:28What is nested loop?
04:29It is also big of N-2.
04:32And how did I do this work?
04:34I did this work.
04:35I did this work,
04:35that I have total work in my loop,
04:38and analyzed it.
04:39Every time I saw my loop,
04:42how many times I am going.
04:43For i is equal to 1,
04:44for 2,
04:45for 2,
04:46for 2,
04:47for 2,
04:47for 2,
04:47for 2.
04:48I have added all the numbers.
04:49Now,
04:50the k is completely ignored.
04:52We wanted to add it.
04:55How did it add?
04:55We could multiply it.
04:58Then multiply it.
05:00Because,
05:00this is the loop,
05:02and then the k is working.
05:03This is the loop,
05:04and then the k is working.
05:05So,
05:06this is the loop,
05:06and the k is working.
05:08Then,
05:08I also multiply it.
05:09But what happens?
05:10The constant is ignored.
05:11That's why the time complexity
05:13will come to N-2.
05:14So,
05:14the complexity will come to N-2.