• 2 days ago
Transcript
00:00What are we going to do next time? We will solve for merge sort.
00:04We will solve the time complexity and space complexity.
00:08Merge sort is also the divide and conquer approach.
00:14What are we going to do here?
00:16We will calculate the recurrence equation or the recurrence relation on the basis of time complexity.
00:23First, how does merge sort work?
00:25We have already written code in detail and analyzed it.
00:30And the time complexity in the video.
00:32I just told you in the lecture that it is so much.
00:35Today we will see why it is so much.
00:37Merge sort is the recurrence function.
00:40We had an array in parameters, a starting index and an ending index.
00:45What was the work?
00:46The work was that we had to remove the array of mid.
00:49So, if I have an array, I will calculate mid.
00:55I already have a starting index and an ending index.
00:59What do I do?
01:00I will call the merge sort in the left part of the array.
01:03Then I will call the right part of the array.
01:05What will happen?
01:06I will call the merge sort first in the left part.
01:09And a second call is the right part.
01:13So, in this way, there are two calls on each level.
01:17Which two calls?
01:18Recursion.
01:18One left part and one right part.
01:21Now, in recursion, these two calls are also a work.
01:25What is it?
01:26Merge.
01:27It is an external function.
01:29There is a function call.
01:30In which I pass all these parameters.
01:33And this function gives me some work.
01:35Now, this function gives me some work.
01:37So, it also takes some time.
01:39It also takes some operations.
01:40And it also takes some time complexity.
01:41So, in this function, there is no time complexity.
01:44So, what can I say?
01:45In a single call, if my merge sort has a base case hit,
01:48then my constant time takes place.
01:50But, this operation will perform constant time.
01:54The merge sort will analyze the calls.
01:56We will analyze the recursive function in the time.
01:59But, this is a merge function.
02:01It has its own time complexity.
02:04It has to be removed from the first time.
02:06Because, in the merge sort,
02:08the merge function counts the time complexity.
02:11So, what will we do?
02:12We will remove the time complexity of this merge function.
02:15So, I wrote something in my merge function.
02:17In my merge function, I created a temporary array.
02:21So, it will become a temporary array here.
02:25It will become an array.
02:27When I add the total array, I have to add the total array.
02:30The total size of the array must be used.
02:34In the worst case,
02:35My half array is N by 2 size.
02:39And the other half part is its size.
02:41This half part is N by 2 size.
02:44In this case, I will become the largest temporary array.
02:50Now, what would I do in this merge?
02:52First of all, there was a loop. Where did I go to this loop?
02:56This loop is doing one-on-one and one-on-one.
02:59There are the left-parts and the right-parts.
03:02I touched all of these elements.
03:05If I talk about the worst case, when I have more parts,
03:09which case will be in my half-parts, and in my second half,
03:14there will be n by 2 elements. In this case,
03:17I can say that the loop will touch n by 2 elements.
03:23And in the other half-parts,
03:27I touch n by 2 elements.
03:30Iterator will go to total elements.
03:36Iterator will touch all the elements in temporary.
03:39Why? Because I have to fill this temporary.
03:41In the worst case, the size of temporary is n.
03:44In the worst case, the size of temporary is n.
03:45In the worst case, the size of left half is n by 2.
03:46Right half is n by 2.
03:48What can I say? Left half plus right half will be n by 2 plus n by 2.
03:53How much will be total?
03:54Total will be n by 2.
03:56Which is also equal to temporary size.
03:58In the worst case, what will I have?
04:00In the worst case, the size of temporary is n by 2.
04:02The size of k will be equal to the size of k.
04:05The k will be equal to this loop.
04:08And the two loops are equal to these loops.
04:10The value of k will be equal to n.
04:12So what can I say?
04:13The three loops will be equal to n.
04:18Which loops?
04:19First of all, I have this loop which is my while 1.
04:23Then I have this loop which is my while 2.
04:27Then I have this loop which is my while 3.
04:30So the three loops will be equal to n.
04:34Or I can say big of n.
04:37Because this loop, k is equal to 0 value is here.
04:41And they will continue to last.
04:43Whether this loop is going or not,
04:44whether this loop is going or not,
04:45whether it is going or not,
04:46whether it is going or not.
04:47But the sum of three will be total
04:50for k is equal to 0.
04:52The total will be equal to 0.
04:55So the time complexity will be n.
04:58So the three of these loops will be O of n.
04:59Now if I will talk about this part,
05:01where I will copy temporary values in my original array.
05:05Where will this loop go from worst case?
05:07In the worst case,
05:09my starting index will be 0.
05:11In the worst case,
05:12temporary.length will be equal to n.
05:16So what can I say?
05:17This loop is my last copy loop.
05:19This will be big of n times.
05:20Which case?
05:21In the worst case.
05:22In other cases, it will be less.
05:24In which case,
05:26I have to call for n by 4.
05:28And put this n by 4.
05:31And put n by 4 put in them to teline
05:31Because it is not the worst case.
05:32In that case my best case would be in temporary..
05:35The left part would be bigger.
05:39In that case
05:39And it will be made of worst case.
05:41That's why I am taking n by 2
05:42Or n by 2
05:42To n by 2
05:43Here I am taking more example of n by 4
05:44Or n by 8
05:46Now I am analyzing the first case of n by 2
05:50This loop has been 0.
05:53of n times and I get these 3 loops and I get big of n times. So what can I
05:59say that
05:59first I will count this time complexity. Then I will count this time complexity
06:05and again big of n. This is my big of 2n. But why don't I write this 2n because
06:112 is a constant which I will ignore. So my merge sort of merge part, which is a function
06:17is that time complexity will come to big of n. So I have figured out that time complexity
06:26will come to big of n and I will talk about space complexity. So it will come to big of
06:31n
06:31because I have used auxiliary space. What is auxiliary space? My auxiliary space is my temporary array.
06:38In the worst case it will come to big of n. So my space complexity will come to big of
06:45n
06:46which is not my merge sort of merge function. Now I have removed the merge function
06:51and I will analyze the merge sort of time complexity and space complexity.
06:55First let's talk about merge sort of time complexity. I was told that
07:00the merge sort of merge is constant. This line is also my constant operation.
07:07This is my recursion. And what is this line of time complexity?
07:11What is this line of merge function? Here is my merge function call.
07:14Merge function's individual time complexity is big of n. So what can I say?
07:20That in every single function call, I will always do big of n work.
07:26Because in every single function call, my merge is called.
07:32And the worst case time complexity is big of n. So in every single function call,
07:37until I don't hit the base case, the rest of the calls will always have big of n time complexity.
07:44So in all the recursive functions, we have constant time in single call.
07:50This time is not constant. This time is called merge function calls
07:54or merge function time complexity. Which is big of n.
07:58Now let's talk about merge sort time complexity.
08:01I have total time complexity. What can I say?
08:04Merge sort of recursive equation will come.
08:06It will come. It will come. If I have a function.
08:10This is my merge sort function.
08:12This is my merge sort function.
08:13It will implement n size array for n size.
08:16So what do I implement this function?
08:18What do I do?
08:19First, I divide my array in two parts.
08:22And what will be the size of both parts?
08:23The size of both parts will be n by 2.
08:26So every time I divide my array by 2.
08:28And then I add two calls.
08:30That means I have called my recursive function
08:33for n by 2 size.
08:35How many times I have called it?
08:36Two times I have called it.
08:37One is my call.
08:39One is my call.
08:41I can change it by changing it.
08:44If I have a function,
08:46this is my merge sort function.
08:48Merge sort function is implemented in n size.
08:51So before this function,
08:53I add a call to n by 2.
08:55I add a call to the left part.
08:57Then I add a call to f of n by 2.
08:59I add a call to the right part.
09:00So I add the same function.
09:02I add array.
09:05What do I do?
09:07I did n work.
09:09How do I do this work?
09:10This work is constant.
09:12I can write it here.
09:14This work is constant.
09:16This work is constant.
09:16This work is constant.
09:17This work is important to merge these parts.
09:22I will merge the time complexity from here
09:24I have a recurrent relation here
09:25If my time complexity is t
09:28for merge sort
09:29I can say this time complexity will be
09:32t
09:33plus
09:34t
09:35plus
09:36my
09:36n
09:37plus
09:37k
09:37I will implement the merge sort of n
09:40time
09:41time
09:41time
09:42time to implement the merge sort of n
09:44time
09:45time to implement the second half of n
09:47time
09:47time to merge
09:49Now we will solve this recurrent relation
09:52k
09:52I will solve