- 2 days ago
Transcript
00:00Now the next time we are going to talk about how we calculate their space and time complexity of recursive
00:06algorithms.
00:07So when we talk about recursion, we will observe two ways of recursion in most cases.
00:12There will be a recursion in which things will work linearly.
00:16It means there will be a main function and it will be doing some work
00:19plus we will solve our other subparts.
00:25One is recursion.
00:28The second is our divide and conquer relation.
00:31We have seen the merge sort.
00:34What did the merge sort function do?
00:35The merge sort first was called for its half part.
00:39Then the merge sort was called for the right part.
00:42Then the merge was done.
00:44What happened here?
00:45The problem has divided itself into two parts and it has done some work.
00:50The merge sort was done in the left part and the right part was done.
00:55It was a merge function.
00:57So when we have a divide and conquer problem, it is our linear recursive problem.
01:04We will use different methods to solve both.
01:07The first method is our total work done method.
01:11We will use linear calls for linear calls.
01:13We are going to remove the total number of calls.
01:16We are going to remove the recursive calls.
01:18We will multiply it by the total number of calls.
01:23We will multiply it by the total number of calls.
01:24Whatever the final answer will be, that will be our total work done.
01:27We will see this for linear calls.
01:28The second method we can remove time complexity is our recurrence equation.
01:33We have seen the recurrence equation in binary search case.
01:36In some way, we will create a recurrence equation.
01:38This is my recurrence equation.
01:41To solve this equation, what will I do?
01:44I will extend this equation on both sides.
01:47Then I will cut things and cut things.
01:48I will cut them and take a final solution.
01:51For this we will also see examples.
01:53These are two ways to solve recursive equations.
01:57If we have to calculate space complexity.
02:00How does the space complexity calculate in recursion?
02:03We know that when recursion runs,
02:05it becomes a tree-type structure.
02:09How does this tree become?
02:10We know that recursion is in the form of stack calls.
02:14What happens in stack?
02:15One is our main function.
02:16The main function will call the other function.
02:19This function will call the fn-1.
02:21This function will call the fn-1.
02:23This function will call the fn-2.
02:26This function will call the calls.
02:28I have to visualize the calls.
02:30I have to visualize these calls.
02:31I can do it in a tree.
02:32Where this function has been called.
02:35Here my fn-1.
02:37Here my fn-2 is called.
02:38This is recursion.
02:40Now we will see how it works.
02:43So here we call tree-type structure.
02:46We call tree-type recursion tree.
02:48This tree-type structure.
02:50The maximum depth is the maximum depth.
02:53The maximum depth is the maximum depth.
02:55I will multiply it.
02:57How many memory is used in a function.
03:00So the multiplication of both these two will give me the space complexity.
03:05We can find this from recursion.
03:07What will we do in recursive algorithms?
03:09First, we will find time complexity.
03:10Then we will find space complexity.
03:13Then we will find space complexity.
03:13Using this approach.
03:15First, let's talk about recursion in factorial.
03:19We have written a function in this way.
03:21The factorial function was named.
03:22There was a single parameter.
03:24What did we do?
03:26We multiplied n by factorial of n-1.
03:30So the call will come to n-1.
03:32How will the stack become?
03:34The stack will become a stack.
03:35This will be the first call.
03:37First, what will be the first call?
03:38First, what will it be?
03:40First, what will it be?
03:41What will it be?
03:43The call will be.
03:43For f of n-1.
03:44What is it doing here?
03:46The call will be.
03:48F of n-2.
03:49And f of n-2.
03:51We will call for f of n-2.
03:54When do it come to n-3.
04:05call i returned 1. So, 1 will multiply here. So, if I call n is equal to 4, then what
04:14will happen? My call stack will see something like that. First, f of 4 will call. What
04:20f of 4 will call me? Call me to f of 3. So, a call frame will be for f
04:24of 3. f of 3
04:26will call me to f of 2. f of 2 will call me to f of 1. And similarly, a
04:33last call will
04:34be for my f of 0. This f of 0, but just as I reached, n is 0. So, what
04:39will I do here?
04:40I will return 1 from here. When 1 returns, 1 will come here. And what will this function
04:43do? This function will be n from this level. 1 will multiply 1 from 1. Now, f of 1 will
04:50return 1 into 1. And f of 2 will multiply 2 from 1 and return 2. What will
04:56do f of 3? 3 will multiply 2 and return 2 to 6. What will f of 4? F of
05:024 will multiply
05:02whatever it has to be, that is 6. And this function will return
05:06main function to value as 24. So, this is how my recursion
05:10works. This is my call stack. Now, in the call stack, every stack
05:14part is utilized in memory and some calls are
05:19going on. So, what have I done? This same call stack, if I
05:32multiply 4. What have I done? F of 2 called and
05:37multiply 3. What have I done? F of 1 called and
05:41multiply 3. What have I done? F of 1 called and
05:42multiply 2. I will do it a little bit. Resize. Now, what have I done? F of 1 called and
05:48multiply f of 0 and multiply 1. F of 0
05:52find out the value. So, this level is my
05:56this is my base case level. In the base case, I know what happened.
06:00Here, you already know value which is 1. 1 will multiply 1
06:04here. Here, you return 1. Here, 1
06:06here, you multiply 1 by 2
06:08and here, 2. Here, you multiply 2 by 2
06:11and here, 2, 3 and here,
06:12you will be back. 3 and 6 will return
06:13and 6, 4 and what will return? 24
06:17So, I can be able to visualize
06:18my recursion in different ways.
06:21One is my call stack
06:22in the form of visualization. One is my
06:24recursion tree in the form of visualization.
06:27Now, what will I do here?
06:28First, I will find time complexity.
06:29find out करती हूं, time complexity के लिए क्यूंकि यह मेरा एक linear type का
06:34recursion है, मतलब इसमें कोई मेरी problem डिवाइड नहीं होगी, सीधा मैं एक और चोटे
06:38level पर, एक और चोटे level पर, एक और चोटे level पर call लगा रही हूं,
06:41तो यहां में simply क्या कर सकती हूं, यहां में simply लिखा लूगी number of calls,
06:45my work done is equal to number of calls, multiply by work in each call, तो मैंने last time क्या
06:54किया था,
06:54इसी formula को मैंने देखा था जब भी linear recursion हो रहा है, तो यहां सबसे पहले number of calls
06:59निकाल लेते हैं, number of calls कैसे आएंगी मेरे पास, number of calls आई इस stack की form में,
07:04यहां पर 4 ने 3 को call लगाया, 3 ने 2 को call लगाया, 2 ने 1 को call लगाया,
07:081 ने 0 को call लगाया,
07:09तो total number of calls कितने निकले, इस n is equal to 4 के लिए, मेरे पास total calls 5,
07:155,
07:16तो क्या मैं कह सकती हूं, on an average, अगर मेरे n की value कुछ भी दी हुई है मुझे,
07:20तो मेरे पास n plus 1 calls होंगे, जिन में से 1 call मेरे main function मेरे recursive function को
07:25लगाया होगा,
07:26मतलब यह वाली जो call है, यह main ने recursive function को लगाया,
07:29तो मैं अगर इसके ऊपर से count करना शुरू करूं, तो 1 call लगा, 2 call लगा, 3 call लगा,
07:344 call लगा,
07:35तो recursive function एक दूसरे को कितनी calls लगाते हैं, अगर मेरे input का size n है,
07:40तो recursion की जो calls होंगी, that will also be equal to n,
07:44तो क्या मैं लिख सकती हूँ, यहापे मेरी number of calls, एक linear recursion,
07:48factorial वाले recursion के लिए n आ जाएगी, क्या हो रहा है, n घटके n-1 होगा,
07:53फिर यह घटके n-2 होगा, फिर यह घटके n-3 होगा,
07:57कब तक reduce होता जाएगा, जब तक last में मेरे पास 0 नहीं रह जाता,
08:00तो इस तरीके से मैंने total number of calls find out कर ली,
08:03अब मैं देखूंगी मेरे हर call में कितना काम हो रहा है,
08:05अगर बात करूं, तो यहां पर यह जो काम है, this is constant work, this is k,
08:12यह वाला जो काम है, यह मेरे actual recursion का काम है,
08:15उसके बाद, इस recursion से जब output आ जाएगा, तो उसको n से multiply करने वाला काम भी constant काम
08:21है,
08:21मतलब, एक ही तो single operation हो रहा है, आपके पास आउटपुट आ गया, उस आउटपुट को बस अब न
08:26से multiply करने है,
08:27तो एक single operation है, इसको मैं constant काम कह सकती हूं, in fact,
08:30इसको मैं constant काम k2 गह सकती हूं, इसको constant काम कह सकती हूं,
08:34तो हर बार क्या हो रहा है, हर बार मेरे रिकर्जन के हर एक लेवल पर single level में,
08:38ये एक लेवल है रिकर्जन का, रिकर्जन के एक लेवल में मेरे पास constant काम हो रहा है,
08:43ना कोई लूप चल रहा है रिकर्जन के अंदर, ना कोई और ऐसा काम चल रहा है,
08:50If you have a loop in which you are running in a loop, then you are increasing my work.
08:52Here, all constant work is done here.
08:54That's why I will write work in each call is equal to a constant.
08:58So, what will be total work done?
09:00Total work done will be n into k.
09:03So, my time complexity will be bigger of n.
09:06Because k is constant, I have ignored it.
09:09So, to calculate the factorial,
09:11In the recursion, my time complexity will be bigger of n.
09:16Now, let's talk about space complexity.
09:20What can I do for space complexity?
09:22My space complexity will be equal to
09:25The maximum depth is multiplied by
09:29How much memory is multiplied by every level.
09:33So, let's talk about the recursion tree.
09:35How much depth is the maximum depth?
09:37Depth or not?
09:38How many calls we put up to the top?
09:40How many calls we put up to the top?
09:42Either we can call it maximum depth,
09:45Or call it call stack height.
09:48Both are right.
09:49If I turn the call stack,
09:50Then my recursion tree will come from one way.
09:53So, what will the height of the call stack?
09:54What will the maximum?
09:55After one point,
09:561, 2, 3, 4.
09:58Until 4 levels, the height of the call stack will go.
10:00If I talk about the recursion tree,
10:02How much depth will it?
10:03It will also be 1, 2, 3 and 4.
10:06So, what can I say?
10:08If my input is n,
10:10Then my call stack height,
10:13Or my recursion tree depth will be the same.
10:16Which will also be equal to n.
10:17So, my maximum depth will come from n.
10:20And how much memory is occupied on every level?
10:22I will talk about every level.
10:24I have no extra variable.
10:25I have no extra array.
10:27I have no extra string.
10:28I have no extra data structure.
10:30I have no extra data structure.
10:30So, how much memory is occupied on every level?
10:33I have no extra memory.
10:35I can say that now we have constant memory.
10:38I have K on I.
10:40It is occupied on one.
10:42So, I have space complexity here.
10:44I have big of n.
10:45Because, there is no extra space used.
10:47Every level is constant space.
10:49It occupies.
10:50The constant memory occupies.
10:51There is only maximum depth.
10:53As many memory occupies it will be,
10:55This factorial recursion will be all the call stack.
10:58In Java, the call stack will become a function.
11:00which will be big of n.
11:05Here I got this one that usually functions
11:08I had to calculate loops for today
11:10If there was no extra variable use
11:15then what was happening? Space complexity
11:17constant. If I had no extra space use
11:20then where will space use?
11:22Where will memory space complexity come from?
11:25Because in recursion
11:28I have a little space in my function
11:30How do I take it?
11:32I store things in the stack
11:33So that's why recursion
11:36will always occupy space
11:38and how it will occupy space?
11:40This space will occupy my recursion stack
11:43which will store all calls in my stack
11:47and will store every function
11:49That's why in factorial function
11:51there is no extra memory
11:52but due to this call stack
11:54because I have space complexity
11:57that will be big of n
11:58So here I will summarize
12:00the two things here
12:02Summary
12:03What we have here?
12:04Summary
12:04In factorial
12:05I have time complexity
12:07big of n
12:09and space complexity
12:10big of n
12:11to be equal
12:12equal