00:00Now we have talked a lot about time complexity, now let's talk about space complexity.
00:04We know that every program requires time to run, some operations perform,
00:09but every program occupies any memory or any space.
00:16How does it occupy this space?
00:18It occupies it in two forms.
00:21One is our heap and one is our stack.
00:24A memory is heap and a memory is stack.
00:27Which memory is in the stack?
00:30Our function calls in the stack.
00:31Then what is it?
00:32Our call stack.
00:34We have seen it in the recursion.
00:36Which memory can occupy it?
00:38It occupies heap memory.
00:40In the heap memory, we create different objects.
00:43The objects that are allocated are in heap memory.
00:48So, I have created a new variable.
00:50I have called a function.
00:52I have created an array.
00:54I have created a string.
00:54I have created another object.
00:57I have created a float type variable.
00:59Or I have created an object.
01:01What is that?
01:02That is that my computer, my java code,
01:05in my computer,
01:06some space or some memory occupies.
01:09And with this memory,
01:10which occupies the relationship with input size,
01:14we call space complexity.
01:15So, we can draw a whole graph here.
01:19We can draw a whole graph here.
01:19The space occupied here will come.
01:22The input size will come.
01:23According to input size,
01:25if my space is increasing and linearly increasing,
01:28I can say that my space complexity will become big of n.
01:32And if there is no space in my program,
01:34I can say that my space remains constant.
01:38So, I can say constant space complexity.
01:41Now, the space is used in a program in two ways.
01:45What is the first way?
01:46The first way is that my input will take some space.
01:48So, I have input an array in my program.
01:52The size of this array is n.
01:53So, what can I say?
01:54The size of this array is n.
01:56The size of this array will take much space.
01:57The size of this program will take much space.
01:58The size of this array will be made in the memory.
01:59The second thing is my auxiliary space.
02:02If you remember,
02:02I have talked about auxiliary arrays.
02:05Auxiliary array,
02:06or temporary array,
02:07or extra space.
02:10Auxiliary array means extra or additional.
02:13So, if I have passed the input size n.
02:15In other words,
02:17I have also made a temporary array.
02:18The size of n.
02:19So, what can I say?
02:20In this program,
02:21the space of input size will be n.
02:23The auxiliary space will also be n.
02:26So, the program uses extra n space.
02:29In the form of a temporary array.
02:31Now, my space complexity is made.
02:35But if we ask the space complexity
02:37or in general,
02:39we have to analyze the time complexity.
02:40In most cases,
02:42we are talking about auxiliary space.
02:43We are talking about time complexity.
02:45Because this input size,
02:46input size,
02:47input space,
02:47in any program.
02:49So, it will not be able to take the input.
02:51In those cases,
02:52we talk about auxiliary space.
02:54If it has extra space or not.
02:56So, my space complexity
02:58is in most cases,
02:59when we are talking about space complexity,
03:01it means intuitively that
03:04we are talking about auxiliary space.
03:06I am giving an example.
03:07I am giving an example.
03:08The example is that
03:10we have seen the merge sort.
03:13What happened in the merge sort?
03:15In the merge sort,
03:16there was always a temporary array.
03:18This temporary array
03:19was always made of n size.
03:22The original array was made.
03:23In the merge sort,
03:24if I have this half sort
03:25and this half sort,
03:27then I have to make a temporary array
03:29completely sort.
03:32So, I used auxiliary memory
03:33I used auxiliary space.
03:35That's why my merge sort
03:37time complexity
03:37is big of n.
03:39Because I used an auxiliary array
03:41and temporary array.
03:43If I talk about quicksort,
03:45there is no extra array
03:46in quicksort.
03:47So, the time complexity
03:48is big of 1.
03:50So, in terms of space,
03:52my merge sort is worse
03:54when it is compared to quicksort.
03:56But yes,
03:57in terms of time,
03:57it is better.
03:58Because in terms of time,
04:00I studied that
04:01the merge sort
04:01is the average case
04:02time complexity
04:03is the worst case.
04:04That is n log in.
04:06In terms of quicksort,
04:07in the worst case,
04:08it is n squared.
04:09In average,
04:09it is n log in.
04:10But we will mostly analyze
04:12this worst case.
04:13So, if we analyze the worst case
04:14with the worst case,
04:15then merge sort
04:17is better performed
04:17in terms of time.
04:19So, we have to see
04:20that I have to keep time
04:21priority
04:21or I have to keep space
04:22priority.
04:23In most of the cases,
04:25in maximum cases,
04:27there is our time priority.
04:30There is no time priority.
04:31Time,
04:32i.e. how quickly
04:33my program is working
04:34for me.
04:35That is my priority.
04:36Because today,
04:37there is a lot of space.
04:38There is a lot of space.
04:40There is a lot of space.
04:41Yes, that is also important.
04:43But in majority of the cases,
04:45Or in your interviews
04:46or contests.
04:48Until the interviewer
04:49does not specify
04:50that the time complexity
04:52is not allowed to keep
04:52I have to keep space.
04:54Until we have to keep time
04:55priority.
04:57Now, what are we going to do?
04:59Next, we are going to do
04:59theoretical analysis.
05:01We are going to do
05:02the actual codes
05:02and start the actual
05:05and determine the actual
05:06method.
05:06What is going to do?
05:07We will solve many
05:08examples of loop
05:08and the time complexity
05:10will be resolved
05:11and we will see
05:11some examples of sorting
05:12and searching
05:13and the time complexity
05:14will be resolved.
05:15And then,
05:16we will analyze
05:18recursive problems
05:19we will analyze
05:20how the time complexity
05:21is used.
05:22We are analyzing it.
