- 14 minutes ago
Transcript
00:00Now let's talk about time complexity.
00:03So what do I do to understand the time complexity?
00:06I take an example of an array.
00:08This array is ARR and I have some elements
00:111, 8, minus 1, 2, 5 and 4.
00:17Now what do I do?
00:18I have to find out my largest element in this array.
00:22I can find out the largest element in any array
00:25which is my linear search.
00:29I will search linearly.
00:32What was the linear search?
00:33I will go to an index and take a global maximum.
00:36I will initialize it with minus infinity.
00:39This is bigger than this.
00:40It will become bigger than this.
00:42Then I will compare it with 8.
00:46I will go to this index with 8.
00:47Then I will go to this index, this is also small.
00:50Then I will go to this index, this is also small.
00:52Then I will go to this index, this is also small.
00:54Finally I will get to know that the largest element of my array
00:58that was it.
00:59This is my linear search approach.
01:01Now in the linear search,
01:03worst case.
01:05That means the worst case
01:07which I have to search more times.
01:09What will happen?
01:10It will be that where my largest element comes from.
01:13My largest element comes from last position.
01:15Like if this is 8, there is 4.
01:18I have swapped both.
01:19Here is 4 and here is 8.
01:21How does my program run?
01:24First of all, the maximum is minus infinity.
01:27I will go here, it will be 1.
01:29Then here, it will be 4.
01:30Here, there is no change.
01:32Here, there is no change.
01:33Here, there is no change.
01:33Here, there is no change.
01:33Here, it will be 5.
01:34Then there is 8.
01:36So, I have done operations.
01:39I mean, how many operations are done?
01:40I mean, how many indexes have done?
01:41I have done work on one index.
01:43To check and update the maximum is equal to 1 operation.
01:48So, I have done operations.
01:49I have done operations.
01:502 operations.
01:503 operations.
01:514 operations.
01:525 operations.
01:536 operations.
01:54I have done operations.
01:54I mean, how many operations have done in the worst case?
01:58I have done 6 times.
02:00Or 6 operations.
02:02I have done 6 comparisons with maximum.
02:05And what is the size of this array?
02:06The size of this array is n is equal to 6.
02:10So, what can I say?
02:11If my size of my array is 1,000,000.
02:13Or my size of my array is small.
02:15My value of n is 1000.
02:17So, I have to do operations in my worst case.
02:21Worst case is not the worst case.
02:23In which my largest element is last.
02:25In that worst case,
02:27I can say that I have to do 1,000 operations.
02:30And if my array size is 1,000,000.
02:32Or if my array is 10 to the power 5.
02:33Then I have to do 1,000,000 operations.
02:37Then I have to do 1,000,000 operations.
02:37Or 1,000,000 comparisons.
02:39So, I have to do a lot of time.
02:41And one thing I am observing.
02:43This is my time.
02:44Just like my value of n.
02:47Just like my array is increasing.
02:49How much time is increasing?
02:50Array was 6.
02:51Then there were 6 operations.
02:53It will be very fast.
02:54But the array is 1,000,000.
02:55So, there are 1,000,000 operations.
02:57So, in 6,000,000 and 1,000,000.
03:00There is a huge difference.
03:01So, I have to do so much time.
03:03Now, if I write a summary here.
03:06What did I find out here?
03:08I found out here that if I apply a linear search.
03:12Then I find out the array.
03:20What is my size?
03:21My size is increasing.
03:24My operations and my program time is increasing.
03:29I mean, that is increasing.
03:31The size of my array is increasing.
03:33The size of my array is increasing.
03:35And when I am increasing?
03:37This is increasing.
03:37I am increasing in my worst case.
03:38The worst case.
03:39The worst case.
03:39That is the worst case.
03:42I mean, my largest element can exist in last.
03:45Now, I will take another example.
03:46Let me consider that my array is a sorted array.
03:50How is the sorted array?
03:51How is the sorted array?
03:52First, there is 1, then 2, then 3, then 4, then 5, then 6, then 7, then 8.
03:57Now, I have to search my largest element in the sorted array.
04:02How will I search the largest element in the sorted array?
04:05It is simple.
04:06It is sorted array and it is sorted in ascending order.
04:08So, it will always be the largest element in last.
04:11So, what do I have to do here?
04:12I have to write a simple line.
04:14What will I do here?
04:15What will I do here?
04:15My largest will be ARR of n-1.
04:19So, how many operations do I have to do here?
04:21I have to do one operation.
04:22Because I already knew that my largest element is always last.
04:27So, I will exist in the last index.
04:28Now, if I consider that my array is equal to 8.
04:33How many operations do I have to do here?
04:35How many operations do I have to do here?
04:37I have to say that I have to do here.
04:37I have to do one operation.
04:39If my array is 1000, then how many operations do I have to do here?
04:44If my array is 1000, then I have to do a sorted array.
04:47Then I have to do one operation.
04:48Why?
04:49Because I always know that this is largest, so it exists in last.
04:51So, in this case, I have to do one operation.
04:54If my array is 1000,000, then how many operations do I have to do here?
04:59Then I have to do one operation.
05:01Because now I have to do one operation.
05:03If it is a sorted array, then my largest element will always exist in last.
05:08So, what can I say here?
05:09I have to perform constant operations here.
05:13I have to perform some operations every time.
05:16I have to perform some operations every time.
05:17Even if my array is small, whether it is bigger,
05:20If it is a sorted array, then I have to perform constant operations constantly.
05:24So, I have to see one case.
05:26My case 1.
05:28What has happened in this case?
05:29In this case, the size of array is n.
05:31What is happening?
05:33My time is increasing.
05:35Time is increasing. I have seen the program in which my operations will increase.
05:39Obviously there will be more operations in any Java program.
05:42So it will take more time to execute.
05:45So my time is increasing.
05:46I have seen the case 2 in which my end is increasing.
05:50But after that, my time is constantly performing.
05:54Or there are constant operations.
05:56So I can remove two relations from here.
05:59In my case 1, one relation is increasing.
06:01My time is directly proportional to my end.
06:04How will it become?
06:05As my end is increasing, my time will increase.
06:09So there will be a relation between these two.
06:11When there is a relation, we can say it in mathematical terms.
06:14Time is a function of n.
06:17That means that the value of n is changing.
06:20Time will also change.
06:21So mathematically it is said that time is a function of n.
06:25I will talk about case 2.
06:27So what can I say in case 2?
06:28That time is not dependent on n.
06:30Time is constant.
06:33Or time is dependent upon something that is constant.
06:37Or time depends on constant operations.
06:39We will perform the same operation.
06:41I can say that time is not a function of n.
06:45Time is independent of input size.
06:47If you increase the size of input size,
06:49Time will be dependent on some constant operations.
06:52So these are two cases.
06:53Now in these two cases,
06:55If I had to find out the largest number in any area,
06:57Then what can I say?
06:59That my first program,
07:00Like the end value of n will increase.
07:03And my second program,
07:04Like the end value of n will increase.
07:06Same time will increase.
07:07So my second program will be more efficient.
07:10In every case,
07:11In every case,
07:11In every case,
07:12In every case,
07:16because if Facebook is writing code, how do people write code for people?
07:19Facebook doesn't write code for 10 people, Facebook doesn't write code for thousands of people,
07:23Facebook doesn't write millions and billions of people,
07:25so we have to look at our own mindset
07:28that our program can handle very big inputs,
07:32so we have to write code for that.
07:34So when we want to see which program is more efficient
07:37or which program is less efficient,
07:39we analyze one thing
07:40and our underlying condition is this,
07:43that we always analyze the big inputs
07:45because our program is so efficient or not,
07:48we don't know how to play four friends.
07:51If we add many people,
07:53then we will know how efficient or not.
07:56So what do we always do?
07:58When we have to see the performance of a program,
08:01when we have to analyze the complexity of code,
08:04we focus on the worst case,
08:05we focus on the worst case,
08:07we focus on the worst case,
08:08which is our input size.
08:11In that case,
08:12if the program is giving good complexity,
08:14it means it is a good program.
08:15If not,
08:16then it is a little less good program.
08:18Now I know here,
08:19that my end will grow much,
08:21then my time will remain constant.
08:23it will remain constant.
08:24So this case 2 program will be more efficient
08:28as compared to linear search
08:30to find out the largest element.
08:32So here,
08:32I have a little idea of time complexity
08:35that time complexity
08:36has a little relation
08:39to my input size.
08:41Input size,
08:42time is increasing.
08:44Now it is possible to increase linearly,
08:46it is possible to increase in quadratic form,
08:49it is possible to increase exponentially.
08:51What does this mean?
08:52What does this mean?
08:53Here,
08:54we have talked about linear search.
08:55In linear search,
08:57the relation is linear.
09:00In linear search,
09:00you know,
09:01in math,
09:01linear graph is something like this.
09:05So,
09:06if my input size has increased,
09:08then in that proportion,
09:10not that much,
09:11in that proportion,
09:12what will increase?
09:13My time,
09:14or my operations will increase.
09:16After that,
09:16it has come here,
09:17in that proportion,
09:18things will increase.
09:20And the output of this way,
09:22that both intersects
09:24in the same line.
09:27So,
09:27when a straight line comes,
09:28a function is a straight line.
09:30What is a straight line?
09:31What is a straight line?
09:31What is a straight line?
09:32It is a straight line.
09:33It is a x plus b.
09:34That means,
09:35you have multiplied with a slope
09:36plus a constant.
09:38This is a straight line.
09:40What is a y is equal to a x plus b.
09:42So,
09:43if the equation is a relationship
09:45with time and input size,
09:47then,
09:47it is a linear relationship.
09:50It is a linear function.
09:52So,
09:52in that case,
09:53I will say,
09:53that the time is,
09:55or the time complexity,
09:59that will be equal to big O of n.
10:02Now,
10:03we will talk about the details
10:04about big O.
10:06But,
10:06I knew that time is directly proportional to n.
10:09Time is not directly proportional to n square.
10:12This is not true.
10:13Time is not directly proportional to n cube.
10:16It is linear here.
10:17So,
10:17time is directly proportional to n.
10:19That is why,
10:20time complexity is equal to big O of n.
10:24Now,
10:24I will summarize this here.
10:26How do I summarize it?
10:28I will summarize it with a beautiful definition.
10:30Beautiful definition is that
10:32amount of space and time taken up by an algorithm.
10:35I mean,
10:36an algorithm,
10:36or a code,
10:37whatever the time is taken up by,
10:39whatever the space is taken up by,
10:41as the function of input size.
10:43Input size,
10:45it relates to the way it relates.
10:47I mean,
10:48time,
10:48or space,
10:50which is a relationship with input size.
10:52That relationship,
10:54that function,
10:55what do we call complexity?
10:57We call complexity.
10:58This is not the actual time taken.
11:00It can be,
11:02a program,
11:03what do we do?
11:06Our array is
11:07n is equal to 6 size.
11:09I am talking about linear search here.
11:12If it is applied in linear search,
11:15if it is applied in linear search,
11:15then it is sorted.
11:17It is also sorted.
11:17If it is understood here,
11:20if it is sorted here,
11:20if it is sorted in linear search,
11:221,
11:232,
11:243,
11:244,
11:255,
11:25then,
11:25it is sorted.
11:26when I look at the last index,
11:27I have started linear search.
11:29What will happen?
11:29It will come here,
11:30here,
11:31here,
11:31here,
11:31here.
11:32Then,
11:33you will get it.
11:34But,
11:34we will get the sorted property directly.
11:37So,
11:37n is equal to 6.
11:39If I consider an array,
11:41in this element,
11:421,
11:422,
11:433,
11:434,
11:435,
11:44and 6.
11:44If it is linear search,
11:46I have 2 milliseconds.
11:50Now,
11:51if I take the value of n,
11:52I will take 1000,
11:53I will take a random time.
11:55This is not related to real life.
11:57In this element,
11:58we think that
11:58it is 100 milliseconds.
12:02So,
12:03what happened here?
12:04Here,
12:04there is a linear search here.
12:06Here,
12:07there is a linear search here.
12:07the size of n is equal to 100,
12:08then,
12:09there is a linear search here.
12:10Time is different.
12:12But,
12:12the complexity of these programs is the same.
12:15Because,
12:16the complexity is not the actual time taken.
12:18The complexity of the time that is run,
12:20it will take a real life time.
12:24The complexity of the time is given.
12:26It tells a relationship.
12:26It tells a real life value.
12:28It tells a relationship or a function.
12:31It tells a relationship.
12:31there is a linear search here.
12:33If you apply a small area or a big area,
12:36the time complexity of the linear search will remain.
12:38That will always be equal to O.
12:40For this case,
12:42for this case,
12:42for any case,
12:43larger than this.
12:44Now,
12:44the value of time complexity,
12:45we can remove two processes.
12:47There are two processes.
12:49First,
12:50our experimental analysis.
12:54We do not use this way practically.
12:56We do not use this way.
12:57It is not important to the placement perspective.
13:00It is not important to the placement perspective.
13:02The other thing is,
13:03our theoretical analysis.
13:04We use this way.
13:05We always use this way.
13:06In the placement of the placement,
13:07we also use it.
13:08In the interviews,
13:09when we write a new code,
13:10we will ask the interviewer to remove the time complexity.
13:12Then,
13:13we will use this way.
13:15Experimental analysis is basically,
13:17that we have written a code.
13:18What do we do?
13:19We use some functions,
13:20some inbuilt classes,
13:21and use it to remove time.
13:22After that,
13:23I will plot that,
13:24if I had a small end,
13:26then what time came?
13:27If I had a medium size,
13:29then what time came?
13:31This is time 1,
13:31this is time 2.
13:32If I had a small end,
13:34then what time came 3.
13:35Now,
13:36I will plot these two.
13:37I will actually plot the code.
13:41Then,
13:42I will plot the time complexity.
13:46This is not practical,
13:47because we will manage our time with input size.
13:51We will always talk about theoretical analysis.
13:55First,
13:56let's talk about theoretical analysis of linear search.
13:59If I talk about linear search.
14:00If I talk about linear search,
14:01then,
14:01I can always show the time complexity in a graph.
14:04I can also show the time complexity in a graph.
14:05What happens in my graph?
14:07What happens in my graph?
14:07In my graph,
14:08my time complexity.
14:10Or,
14:11I can also say operations,
14:13operations will increase.
14:14If operations are more than in a program,
14:17then the time complexity is more than in a program.
14:19Unless and until,
14:20it is not constant operation.
14:21If the operation depends on input size,
14:24then the time complexity will increase.
14:26And here,
14:26my input size.
14:29As I observed,
14:32in my array,
14:33that,
14:33as my input size was small,
14:36it was a little less time.
14:38As I said,
14:38my input size is a little less time.
14:40What do I feel?
14:41I feel a little more time.
14:43And,
14:43as I said,
14:44my input size is a little more time.
14:46This is my worst case.
14:48This is my worst case.
14:49This is my worst case.
14:49It tends to infinity.
14:50I mean,
14:51you can also increase the time complexity.
14:52In that,
14:53my time complexity is more than in.
14:55I can say,
14:56this will meet something here.
14:57I can meet something here.
15:00I can meet something here.
15:01I can meet something here.
15:05I can meet something here.
15:05if I want to make a relationship,
15:07a relationship in mathematics is nothing but a function.
15:11So,
15:11if I want to make a function under them,
15:13that function will show something like this.
15:15And,
15:16that function is going linearly.
15:17Linearly is like straight line.
15:20I mean,
15:21I touch it on the same line.
15:24I touch it on the same line.
15:25So,
15:26what can I say?
15:26If my input size is very big.
15:29I mean,
15:30my input size is so big.
15:32So,
15:33I can figure out that
15:34my time,
15:36obviously,
15:37from the old,
15:37small,
15:38small value.
15:39will increase.
15:40But,
15:41my time complexity is this straight line represents my complexity.
15:47What is actual time taken?
15:49What is actual time taken?
15:50It will plot here.
15:52Where is the input size?
15:53It will plot here.
15:55But,
15:55where will we plot?
15:56Time complexity is a line.
15:59This is my time complexity.
16:01This is not my time complexity.
16:02And,
16:03what is the function in this time complexity?
16:05What is the function in this time complexity?
16:06Y is equal to
16:07ax plus b.
16:09Now,
16:10what was here?
16:11Y was my time.
16:13So,
16:14what can I say?
16:14My time is a relation of n
16:16plus b.
16:18So,
16:18my time complexity is equal to big of n.
16:21What do we do?
16:22We ignore all the constants of time complexity.
16:25This is also a constant.
16:26This is a constant.
16:27Which is the input size?
16:28The input size is only n.
16:29So,
16:30what did I do?
16:30I took my time complexity in n terms.
16:33Now,
16:34we will explain this in detail.
16:36But,
16:36I can now understand that
16:37in linear search,
16:38why is it called linear search?
16:40Because,
16:40there is a linear relationship
16:41between the input size of time.
16:44So,
16:45this is what time complexity is.