Basics of Asymptotic Analysis: Comparing Array vs Linked List Efficiency

In this presentation and in the subsequent presentations, I'm going to discuss about the basics of asymptotic

analysis. And this is just part one of that. So, let's get started. I'm going to discuss the definition of

data structure once again. A data structure is the organization of the data in a way so that it can be used

efficiently. We want to use our data efficiently and we want to perform some operations on it. For this purpose, we

are using the data structure which is efficient in terms of storing the data. And if we want to use our data, we would

be able to use it efficiently. This is the definition I have taken from the previous lecture, right? Now, this

efficiently term is very important. In order to use data efficiently, we have to store it efficiently. There is no

doubt about it. We have to store our data efficiently if we really want to use our data efficiently. Now, let's

discuss the efficiency in more details. Efficiency of data structures is always measured in terms of time and space. Let

me tell you when efficiency comes, it is always measured in terms of time and space. So, what is the picture of an

ideal data structure? An ideal data structure could be the one that takes the least possible time for all its

operations and consumes the least memory space. Both these things should be less. It should take the less amount of time

for all its operations and should consume the least memory space as well. Then I can say a data structure would be

an ideal data structure. Isn't that so? Now, our focus will be on finding the time complexity and not the space

complexity, let me tell you. We are not interested in finding the space that how much space a data structure will

consume. We are right now interested in finding the time complexity for easing our task, okay? So, by finding the time

complexity, we would be able to guess which data structure would be the best, okay?

Now, there is one question. On what basis we could compare the time complexity of the data structures? This

is a very important question, let me tell you. We are going to compare the data structures, right? Now, how we can

compare the time complexity of the data structures? On what basis we will compare it? We will compare the data

structures on the basis of operations performed on them. Now, let me give you an example and the whole concept will be

clear to you. Let's take an example of an array, okay? Let's say we have these many elements in

our array. Right now, the size is not defined, but just think of this that this array is capable of storing 100

elements and right now we have eight elements in this array. Let's say our target is to add data at the beginning

of the list. This operation we want to perform on this array. Array is a data structure. We want to perform this

operation, that is adding data at the beginning of the list. And I want to know that how much time it will take.

Let's study this properly. Let's say we want to add this particular element at the beginning of the list. Now,

obviously this element is trying to reach this particular place slowly. There is already an element at the

beginning of the list, isn't that so? There must be an empty slot available in the array. As I've already told you, my

array is capable of storing 100 elements. So, obviously there is an empty slot over here. Now, what we will

do is we will shift all the elements towards right. These elements we will shift towards right so that there should

be an empty slot over here. Then we can easily add our element at the beginning of the list. Oh my god, there's so much

hard work, right? If we want to add an element at the beginning of the list and that too an array, it would be very

difficult task. We have to shift our elements towards right and then we can add our element. Let's take another type

of a data structure, that is linked list. Linked list is nothing but sequence of nodes connected with each

other. Here we have this node which contains some data and it also contains the address of the next node, okay? Now,

the difference is that an array is stored in a contiguous fashion, that is obviously if the address of this

particular element is 1,000, then the address of the next element will 1,004. If I'm assuming that size of integer is

4 bytes, right? But here it is not important. It might be possible that the address of the one node is 1,000 and the

address of the next node is 2,000. It could be any address. It just stored the address of the next particular node so

that it can be linked to the next node. So, this is what a linked list is all about. And obviously, there is a head

pointer which is pointing to the first element of the list so that we can reach the first element and then after that we

can reach the other elements as well. This is what a linked list is. Okay? Now, let's say we want to add this

particular data in the beginning of the list. Now, how do we do that? We definitely have to store the address of

this particular node over here, right? So, let's replace this by 1,000. Now, by adding this address, it will point to

this particular location. Now, this node is linked to this node. After that, we just change the head pointer and it will

now point to this particular location. With this idea, we would be able to add our element at the beginning of the

list. Previously, the head pointer was pointing to this particular node. Now, it is pointing to this node. This is the

new node which has been added at the beginning of the list. Isn't that so? Is this operation tedious? No, not at all.

This data structure is much efficient in adding data at the beginning of the list in comparison to the array. Isn't that

so? So, what is the conclusion? Inserting an element at the beginning of the list is way faster in the linked

list than arrays. If you want to add data at the beginning of the list, then it is much faster in the case of linked

list than arrays. In this way, we can compare data structures and this will ultimately give

the idea to select the best possible data structure for a particular operation, right? Obviously, in this

way, we would be able to compare data structures and then we can select the best possible data structure for a

particular operation. Here, we are performing an operation that is adding the data at the beginning of the list.

It is clear that linked list is performing better than array, right? So, definitely, we will choose linked list.

So, this way, we can compare the data structures and this will ultimately give the best possible data structure for a

particular operation. That is why we are studying time complexity. Because with the time complexity, we would be able to

know that which operation on which data structure will take less time. In the subsequent lectures we will learn more

about the time complexity, how to find the time complexity, how do we able to compare the data structures. Obviously

the previous example was a very simple example. Sometimes it is difficult to understand which particular data

structure is better than the other data structure. That is why studying time complexity is very important. This will

help us in determining which data structure is better for a particular operation.

Okay friends, this is it for now. Thank you for watching this presentation.