- 16 minutes ago
Transcript
00:00What will I do? I will solve the recurrence relation for my merge sort
00:03So I have written tn is equal to t of n by 2 plus t of n by 2
00:08I can write here n only here or my nk will be n into some constant
00:14I know that n plus k will always increase nk
00:20If my k is positive, I have written nk and I have ignored that constant
00:25I can also summarize this in a best form
00:28That t of n is equal to 2 times t of n by 2 plus my nk
00:33What happened? I have combined these two terms and 2 times
00:36Because the left half will be the same time complexity
00:39The right half will be the same, so I have 2 times
00:43So we take the upper level and take this value here
00:47What can I say?
00:48I can say that t of n by 2 will be equal to 2 times t of n by 4
00:54plus n by 2
00:56What do I do? I have replaced this n by 2
00:59This n by 2
01:01This n by 2
01:01This n by 2
01:02This n by 2
01:02Now I want to cut this term from this term
01:06In the recurrence relation
01:07Because we add the terms
01:08And add the terms
01:09But here
01:09There is a 2 multiplied
01:11So I will multiply the whole equation in this equation
01:14So I will multiply the whole equation
01:14As we multiply the whole equation
01:162 will come here
01:17This will become 4 equal to this
01:19And 2 will come here
01:21Now I will write the next equation
01:22So t of n by 4 will be equal to 2 times t of n by 8
01:26Plus n by 4 into k
01:29Now I want to cut this term from this term
01:32I have to cut heart
01:32And here I will multiply the whole equation
01:36Here and here I am adopted
01:37If it is plus 4
01:37Suppose I lift up here
01:39Here we have 8
01:40And here we have 4
01:42Else I will add G
01:42This is n by 2
01:43Next term
01:43I am also displayed
01:44This heavy term
01:44T of n by 8
01:45Is equal to 2 times t of n by 16
01:48Plus n by 8 into k
01:51Now what do I got to do?
01:53I have to chop this term from the term
01:54So here you will multiply the whole equation
01:58So I have multiplied the whole equation
02:03I will multiply this with 8.
02:05Similarly, this time is less.
02:08First, n was half.
02:09Then, n by 2. Then, n by 4. Then, n by 8.
02:11In the last time, there will be t of 1.
02:14And who will be equal?
02:15This will be equal to constant time.
02:19Or I can call this big of 1.
02:20This will be my constant time.
02:23What I have observed now?
02:24I will cut the terms.
02:26This term is equal to this term.
02:28This term is equal to this term.
02:29This term is equal to this term.
02:31This will be cut from any other term.
02:33And there will be no term in the above equation.
02:35That will cut it from here.
02:37So, my resultant comes from here.
02:39What does resultant say?
02:40What is left hand side?
02:41What is left hand side?
02:44It will be constant time.
02:46It will be only this value.
02:48And there will be the right terms.
02:50Which will be my final answer.
02:53What will I say?
02:55What will this happen?
02:55What will this be?
02:56What will this be?
02:57Nk.
02:58What will this be?
03:00Nk.
03:00What will this be?
03:02Nk.
03:03From this last time, I will see Nk.
03:06And how will this be?
03:08It will be x.
03:10That I have x equations.
03:12So, if I have x recurrence relations.
03:15So, what can I say?
03:17What can I say?
03:18I can say x.
03:19To say x,
03:20It means that the value first was N.
03:22Then, N by 2.
03:23Then, N by 4.
03:24Then, N by 8.
03:26Then, N by 8.
03:42I will write N by 2 to the power 1.
03:43I will write N by 2 to the power 2.
03:45I will write N by 2 to the power 2.
03:47I will write N by 2 to the power 3.
03:48Similarly, this will be N by 2 to the power x.
03:50Because these are x levels.
03:51So, what can I say?
03:53If I divide N by 2 to the power x,
03:55then its value is 1.
03:57So, N will be 2 to the power x.
03:59Now, if I take the two sides log.
04:01So, log base 2.
04:02N will be my x.
04:04So, what will x value be?
04:05x value is log n.
04:08I will write this in the binary search.
04:09This is also in the binary search.
04:10This is also in the more sort.
04:12In fact,
04:13when you observe this pattern,
04:15that N is always half.
04:16This is also half.
04:17This is also half.
04:18This is also half.
04:19This is also half.
04:19This is also half.
04:20And, it is half.
04:21So, how many steps will be half?
04:23Log n steps will be half.
04:25We will remember that.
04:26How many steps will be half?
04:27Log n steps will be half.
04:29So, my x value is log n.
04:32I will give this to God.
04:35So, what can I say?
04:36How many steps will be here?
04:38My x value is log n times.
04:41So, I can say this.
04:43Plus, log n multiplied by n.
04:47Because, here it was only tn.
04:49Here it was only constant time.
04:51The rest of the terms were cut.
04:52And, here it was only n.
04:55How many steps did it get?
04:56How many steps did it get?
04:57So, I have done log n multiplied by n.
05:00Now, let's simplify this.
05:02Using the rules of big O.
05:04What are the rules of big O?
05:06This is my tn.
05:07This is my time complexity.
05:08What will be the time complexity?
05:09What will happen?
05:10The first rule of big O.
05:11Ignore constants.
05:12Ignore constants.
05:12Ignore constants.
05:13Then, I will also ignore this.
05:15I will also ignore this.
05:15My k will also ignore it.
05:16Now, what is the rule of big O.
05:17What is the majority term?
05:19What is the majority term?
05:21Log n multiplied by n.
05:22So, what can I say?
05:23My time complexity will be n multiplied by log n.
05:27Log n n.
05:28I have written n log n.
05:30It's the same thing.
05:31So, my time complexity is the merge sort.
05:33This is the reason why n log n.
05:36Because every time, my calls will be log n time.
05:41And how many single calls will be n?
05:44I can visualize it.
05:46This is the reason why I started out of recurrence relation.
05:48If I had to start out of another way,
05:50So, what could I say?
05:52If my value is 5.
05:54So, how does my recursion look?
05:56First of all, my calls go to 5.
05:58Then, the other calls go to f of 2.
06:01This is my f of 2.
06:04Then, the calls go to f of 1.
06:06This will be f of 1.
06:08This will be f of 1.
06:08This will be f of 1.
06:09This will be f of 1.
06:10So, it becomes a recursion tree.
06:13Every time you see my value half.
06:16This is n by 2.
06:17This is n by 2.
06:19This is n by 4.
06:20This is n by 4.
06:21So, this will also go to log n levels.
06:23Which we have learned now.
06:25I will create a general tree.
06:27How will the general recursion tree look?
06:29My f of n call will be f of n by 2.
06:33This call will be f of n by 2.
06:35This call will be f of n by 2.
06:36This call will be f of n by 4.
06:38This call will be f of n by 4.
06:40This call will be f of n by 4.
06:42This call will be f of n by 4.
06:45This call will be f of n by 4.
06:45In the same way, this call will be f of n by 8.
06:47When will these calls go down?
06:50They will go down when I don't reach f of 1.
06:52So how much depth is?
06:54Depth is when I don't reach n to n.
06:58So every time I divide from n to 2.
07:00When will I reach 1?
07:01How many levels will I reach?
07:03Login levels will I reach.
07:04So can I tell you what I have done?
07:07That I have worked on recursion time complexity
07:08and work done.
07:09What happens when we reach levels
07:11This is my total number of calls
07:15or total depth of my recursion tree.
07:17How many levels have I reached?
07:19I went to log in level.
07:21And how many levels have I worked?
07:24I work in one level with n.
07:26Where does n come from?
07:27From my merge function.
07:29So what can I say here?
07:30My merge sort time complexity turns out to be
07:33Login into n.
07:35In the worst case,
07:37In the worst case,
07:39Merge sort time complexity is important.
07:41Which is n log in.
07:43If I talk about space complexity
07:46I use a auxiliary array.
07:48Where do I use?
07:48In my merge function.
07:50In the merge function.
07:50In the merge function,
07:51There is only one thing used.
07:52Plus, there is a constant space
07:54which is used in variables.
07:56So how much time did I take?
07:58I took time for big of n.
08:00That's why merge sort time complexity is n log n.
08:03And space complexity is big of n.
08:05And this is why space complexity
08:06because we use temporary array
08:08to merge sort.
08:10In the merge sort.
08:10And this is why