• 14 minutes ago
Transcript
00:00Last thing, let's talk about how we have to approach questions when we solve questions.
00:05Our approach should be that first, let's put brute force.
00:09Brute force means whatever logical thing is in our mind.
00:13Whether it's time complexity or space complexity,
00:17first of all, I have to think about brute force or direct solution.
00:21What do we do? Let's try to build logic, solve paper pen.
00:25And we have to start a brute force solution.
00:28Now, as I have to start a brute force approach,
00:31now I have to optimize it.
00:34How to optimize it in terms of time?
00:37First of all, let's see how I can start the best time.
00:42Like the beginning of the equation.
00:44If I have an array, let's take a sorted array.
00:48In which I have some elements.
00:49And what do I have to do? I have to start the largest element.
00:52So, first of all, I have to search for the largest element.
00:56So, I can start a linear search here.
00:58So, first of all, I will see what I have to do with brute force.
01:03I have to start a linear search.
01:04Then, I will know that linear search is bigger of n time complexity.
01:08So, I will think about better search time complexity.
01:11Then, I will think that I can start a binary search here.
01:14Then, I will analyze that binary search time complexity is with login.
01:18Then, I will think that there is better time complexity from login.
01:22Then, I will think that my array is sorted.
01:25In the sorted array, we have to start the largest element.
01:28So, what do we always do?
01:29The last element is the largest.
01:31So, what do I do?
01:32I will follow direct approach.
01:34In direct approach, I will always have constant time complexity.
01:38So, the best time complexity of solving this problem is constant time complexity.
01:43In my mind, if I don't click in the beginning, there is no problem.
01:46We will start with brute force, which we will go to linear search.
01:49Then, we will optimize it a little bit.
01:51Then, we will optimize it a little bit.
01:52And we will reach the most optimized solution.
01:55Now, one more special thing.
01:57When we go to online platforms or sit for interviews,
02:01What does it give us?
02:02In every question, we give us an input size.
02:06Input size.
02:07Input is possible to show us an array.
02:10If my input size is n, then the value of n will always be less than 10 to the power
02:14of 5.
02:15Or less than 10 to the power of 8.
02:17Or less than 10 to the power of 12.
02:19So, in this way, my input gives us an input.
02:22Now, I can guess that the time complexity of my solution should be in a range.
02:29Like all of my online judges.
02:33Or if I participate in a contest where I participate in a contest or on-line platform,
02:38I practice on-line platform.
02:39How much time allows for solving a problem?
02:42Usually, the time allows is equal to 1 second.
02:46And approximately, we can perform 10 to the power of 8 operations in one second.
02:52I am going to take an example.
02:54Let's assume that the value of n is given to 10 to the power of 6.
02:57And my job is that I have to search an array in one second.
03:03So, if I apply a linear search here,
03:05Then in linear search, there will be approximately 10 to the power of 6 operations.
03:08Because the time complexity of linear search is bigger of n.
03:11But here, if I apply a binary search,
03:13In which time complexity is equal to log in.
03:15So, how many operations will I take?
03:17My operations will be log of 10 to the power of 6,
03:20Which is approximately 30 operations.
03:22So, what will happen if I apply a linear search,
03:25Then this code will also work.
03:27Because maximum 10 to the power of 8 operations are allowed.
03:30And I have solved in 10 to the power of 6.
03:32But if my input size n is equal to 10 to the power of 9.
03:36So, what will happen in this case?
03:38In this case, a linear search will take approximately 10 to the power of 9 operations.
03:41And a binary search log of 10 to the power of 9.
03:44So, approximately, if I have 20 operations here,
03:48Then I will have 30 operations here.
03:54So, in this case,
03:56Because 10 to the power of 8 operations are allowed in online contests.
04:00So, if you apply a linear search,
04:02Then you will have an error of time limit exceeded.
04:06So, in this case,
04:07Our code is not optimized.
04:09We will have to optimize it more.
04:11So, I will apply a binary search here.
04:13Because it will only be 30 operations.
04:15So, if I know that my input size is bigger than 10 to the power of 8.
04:18So, if I know that my input size is bigger than 10 to the power of 8.
04:19So, I will not apply a linear search.
04:21I will always apply a binary search.
04:23Because there are operations in there.
04:25If there are operations in there,
04:26So, time will be less.
04:27Because for 10 to the power of 8 operations,
04:29If it is 1 second allowed,
04:31If it is 1 second allowed,
04:32So, if we do operations above this,
04:34Then there will be more time.
04:36So, there will be this error.
04:38Which is time limit exceeded.
04:41So, if time limit exceeded,
04:44When we have to participate in online contests,
04:46Or at the time of the interview,
04:48Then we should understand that
04:49Our approach is correct.
04:51But we have to optimize it more.
04:53That means,
04:53For some steps,
04:55For some steps,
04:55For some steps,
04:56For some steps,
04:56For some steps,
04:57To solve this question in a better time complexity.
05:00So, I hope that,
05:01We will learn a lot of things from time complexity.
05:04We will not only see these things theoretically.
05:07Whenever we participate in a contest,
05:09Or we solve some questions.
05:11In fact,
05:11We are also solving some practice questions.
05:13Or we have seen a lecture,
05:15In which there is a question solved.
05:16So, we have to pause it,
05:18And calculate time complexity.
05:20And the more we practice the process of time complexity,
05:25The more we will be better.
05:27And time complexity is something,
05:29That will always be asked in interviews.
05:31That means,
05:32In 95-96% of the interviews,
05:35That will always be asked in interviews.
05:35Therefore,
05:36Time complexity,
05:37And space complexity,
05:38Which is our topic.
05:39This should be strong when we talk about DSA.