In this video, we are going to analyze the time and space complexity of common operations on arrays.
Now these are the operations that we will analyze accessing from an array, setting the value at a particular
index in an array with a value traversing the array, copying the array and creating a new array.
Inserting to the array at various positions and removing from the array at various positions.
Now, knowing the time and space complexity of these common array operations is important to analyze
the complexity of algorithms that we are going to write in the future.
Videos.
All right.
So let's get started.
First we look at accessing from the array and setting the value at a particular index in the array.
Now these two have space and time complexity of O of one or constant time and constant space.
All right.
Now why is that.
So let's say we have the array over here.
Now let's say the values in this array is one nine, eight and five.
And the indices are zero, one, two and three.
Now let's say we want to access the element at index three.
So let's call this array r.
All right.
So if we say r at index three we can directly access this right without traversing the array.
So accessing this over here is a basic operation.
All right.
And the way this works is again remember when we say that this is a basic operation and it works in
constant time even if the array is very big.
Let's say it has hundreds of elements.
And we want to access the element at index 100.
All right.
For example.
Then also it's going to take the same time as accessing this element over here, which is pretty near
to the beginning of the array.
So the time for accessing the element, whether the array is very big or very small, is going to be
the same.
Now, if we want to access this element over here, what we will do is we will take the memory slot
where this is stored.
All right.
So again these elements will be stored in memory slots.
And for each element or each value that you are storing, maybe we will have four memory slots or some
constant number of memory slots.
Now with respect to coding interviews it's not required to know that.
But again it's going to take some memory slots to store each value.
So if we want to access the value at index three, what we will do is we will take this slot address.
And then to that we will add three times the slot addresses needed per element.
So directly we can come over here without traversing the array.
So that is why over here accessing and setting values in an array is a constant space and time operation.
So we are not traversing the array for this.
So that's why it's constant time.
And it is constant space.
Because you can see we are not using any auxiliary or additional space, right.
We just have the value.
We come over here, we access the place.
And if we want to access we read it.
If you want to set the value, we come over here and then we overwrite the value over here.
So we are not using any extra space as well.
All right.
So let's continue.
The next operation is traversing the array or searching for an element in the array.
Now for this the time complexity is O of n and the space complexity is constant space.
All right.
Now why is this O of n.
Let's say we have an array.
Let's say it has n elements.
All right.
And let's say we are searching for a particular element.
Now in the worst case it can be the last element right.
So we have to move through every element.
All right.
So that is n operations if there are n elements in the array.
And again if you are traversing the array the array also we are moving through all the n elements.
Now we can say that it's actually O of a constant into n because one element is stored in not one memory
slot, but maybe four or a constant number of memory slots.
Right now we would have to traverse all the memory slots.
But then again, this constant over here, as you have seen in the previous video, we can neglect it
when we do the Big-O analysis.
So that's why traversing an array or searching for an element in an array is an O of n time operation,
and the space complexity is O of one, because as you can see, we are not using any additional space,
we are just moving through the array.
Right?
We are not creating a new array or a new hash table, etc. so we are not using additional space.
So that's why it's O of one space complexity.
All right.
Now let's proceed.
Let's say we want to copy the array which we have and create a new array.
All right.
So we are making a copy of the array.
In this case space and time is going to be equal to o of n.
Now why is that.
So for again with respect to space we are creating a new array.
Right.
And the new array is also going to have n elements.
So that's why we will need new memory slots.
All right.
So that's why the space complexity is O of n.
And the time complexity is also O of n because we have to traverse the given array.
Let's say this is the given array.
And let's say it has three elements.
So we have to go through each element and then copy it and create a new array with these elements.
Right.
So we have to traverse the given array also.
So that's why the time complexity is O of n.
All right.
So copying an array and creating a new array is space and time complexity of the order of n.
Now let's proceed now before we go ahead and look at.
Inserting elements into an array at different positions.
Let's take a quick look at how an array is stored in memory.
Now let's say this is the array which is given to us again.
And we know an array is an ordered list.
So we have zero, one, two and three as the indices for this array.
Now to store each element certain number of memory slots will be needed.
Now let's say we need four memory slots over here four memory slots over here four memory slots to store
this, eight and four memory slots to store this five.
Again, we're not going into greater detail over here because that's not required with respect to coding
interviews.
Now the interesting thing to notice over here is that we need these 16 memory slots, which is four
plus four plus four plus four.
That's 16 memory slots.
We need them back to back.
All right.
So let's say these are the memory slots.
Let's say this is our memory canvas.
So let's just have some spaces over here.
Let's say this is slot one.
And then this keeps going on till slot 16.
So we are taking 16 memory slots back to back.
So that's important for arrays.
We can't have one memory slot somewhere and the other second memory stored somewhere else.
We need the memory slots back to back.
Now the implication of this is that let's say we want to insert something over here.
Now we are not sure that this is empty.
Right.
This may be used by the computer for something else.
So this is the interesting thing to notice over here.
Again the same thing applies when we want to insert over here as well.
Right.
We don't know if this is empty.
All right.
So having known this that is in the case of an array the memory slots are required to be back to back.
All right.
Now let's again come back to the list where we are discussing the common operations on the array.
Now we are over here.
We are discussing insert right now when it comes to insert there is an interesting concept over here
which is static arrays and dynamic arrays.
Now in the case of dynamic arrays again we have in the case of JavaScript and Python all arrays are
just dynamic arrays under the hood.
But when you talk about programming languages such as C plus plus or Java, we have both of these.
So we have to define whether an array is a static array or a dynamic array.
Now in simple terms, a dynamic array is just an array that allows an O of one or constant time insertion
at the end.
So that's the concept of a dynamic array.
And in the case of a static array it's a fixed it's an array of fixed size.
All right.
So the next memory slot as we have seen previously may not be empty if we want to insert something over
there.
But in the case of a dynamic array, the operating system will allocate almost two times as much as
memory is needed so that we can insert at the end to a dynamic array in constant time.
So this is how a dynamic array works.
Now we can say that it's actually not technically always constant time.
It's going to be constant time on an average.
Or we can say it's amortized constant time.
Now, this means that in some cases initially over here, we have seen that let's say we are saying
we are creating an array in JavaScript of size four.
Now the operating system will allocate almost two times as much as memory is needed.
So that's almost eight size right to store eight elements.
Now when we're done with storing eight elements and when we are pushing the ninth element, at that
time the memory will allocate again another nine more memory slots.
So at that instance it's not going to be an O of one operation.
But then on average right.
You can see in most cases again we are getting nine new slots.
So if we even push nine more elements it's just going to be O of one.
So we can say on an average, in the case of a dynamic array, insertion at the end is a constant time
operation.
All right.
So let's continue.
Now let's take a look at these three positions.
So we want to insert maybe in the array at the beginning at the end or somewhere in between.
Now if you want to insert in an array at the beginning, let's say our array is one two, three.
And we want to insert over here zero so that the array becomes zero, one, two, three.
Now if you want to do this this is a O of n time complexity operation.
Why is that so.
Because again we don't know whether this memory slot over here is free.
So what we have to do is we have to copy the array and make a new array with the required number of
memory slots.
So that is why this is going to be an O of N time operation.
All right.
Now if we want to insert at the end in the case of a dynamic array.
And for JavaScript it's always a dynamic array.
So in the case of a dynamic array this is a O of one or constant time operation.
Now if it is a static array then it's an O of n time operation because we don't know the whether the
next slot is empty or not.
But as we discussed in the case of dynamic arrays, this is a O of one time operation because the operating
system allocates extra space when it creates the array.
So a dynamic array, in short, is just an array that allows a constant time insertion at the end.
Now let's proceed now if you want to insert somewhere in between, that is probably let's say insert
over here, we want to insert a value in between 1 and 2, which is let's say four.
In that case this is going to be a O of n time operation.
Because again we have to make a copy of the array and we have to re-index the elements.
All right.
So even in the case of a dynamic array over here we will have to shift the elements.
And again for that it's going to be a O of n time operation.
And you may think that we're not shifting all the elements.
For example over here we are just inserting and then shifting these two elements.
But then remember if we say that the time complexity is of the order of, let's say one by four into
n, this is just a constant and we remove it and we say that this is still an O of n time complexity
operation.
Now for all these three that is inserting at the beginning, at the end or somewhere in between, the
space complexity is just O of one or constant space.
Because again, we are not using any auxiliary space like creating a new array or a hash map, etc..
Now let's proceed.
Now we come to removal.
When it comes to removing.
If we want to remove from an array, let's say this is the array one, two and three.
If you want to remove from the beginning, then we'll have to shift these positions and re-index them.
Right.
So initially this is zero one and two.
Now if you remove this this is going to be zero.
And this is going to be one.
So we have to shift the elements and re-index them.
So removing at the beginning is going to be an O of n time operation.
Now removing from the end is a O of one or constant time operation because we don't need to re-index
anything.
Right.
So we have zero and one over here and we are just removing this over here.
So we are freeing up this memory.
So that's a constant time operation.
It does not require shifting the elements.
And if you want to remove somewhere in between again that's a O of n time complexity operation because
we would have to shift around the elements and re-index the elements.
Again, we have discussed that even if we have to move around only, let's say one fourth of the element.
In that case it's a O of one by four into n uh, time complexity.
And this is a constant.
So we just remove it and still we say that it's a O of n time complexity operation.
Now in these three cases when we talk about space complexity, it's again constant space.
Because we are not using any additional space.
We are not creating a new array or a hash map, etc..
So these are the six things that we have discussed over here.
Now let me just summarize this over here.
Accessing from an array has constant space and time.
Setting a value in an array is constant space and time.
Traversing the array is O of n time and space is constant, right?
You can see except copying an in an array, copying an array, and creating a new array.
In all the other cases, space is O of one, but over here space is O of n because we will need n memory
slots, right?
Or N into a constant number of memory slots for the new array, and copying is an O of n time complexity.
Operation.
Inserting at the beginning is O of n time.
Inserting at the end is O of one time for the case of a dynamic array and inserting somewhere in.
Between is o of n time.
All right.
And removing at the beginning is O of n time.
At the end is O of one or constant time, and somewhere in between is O of n.
So notice that in the case of a dynamic array, we can insert at the end.
All right.
So that's O of one.
So that's efficient.
And then insert and removing from the end is also O of one.
So these are good operations.
Or these operations have good time complexity when it comes to an array.