CODEWITHSUNDEEP
arraysdata-structureslinked-listtime-complexitybig-o
amy
amy

Reputation: 644

Time complexity of sequentially scanning an array vs a linked list?

Since the elements of an array are stored contiguously in memory, I understand that sequentially scanning all the elements of an array would be much faster than in a linked list of same size. For the former you only have to increment some index variable and then read the value at that index whereas for LL you have to read pointers and then fetch data at non-contiguous memory addresses. My question is specifically how we would categorise these two cases in terms of time complexity?

For scanning array, does perfoming n * random accesses i.e. O(1) operations mean that overall it becomes O(n)? In that case wouldn't both be O(n)?

Sorry if this question doesn't make sense, maybe my understanding of time complexities isn't so good.

Upvotes: 1

Views: 1306

Answers (3)

templatetypedef
templatetypedef

Reputation: 372872

You are correct that

  1. sequentially scanning a linked list or an array takes time O(n), and that
  2. it's much faster to scan an array than a linked list due to locality of reference.

How can this be? The issue has to do with what you're counting with that O(n). Typically, when doing an analysis of an algorithm we assume that looking up a location in memory takes time O(1), and since in both cases you're doing O(n) memory lookups the total time is O(n).

However, the assumption that all memory lookups take the same amount of time is not a very good one in practice, especially with linked structures. You sometimes see analyses performed that do this in a different way. We assume that, somewhere in the machine, there's a cache that can hold B elements at any one time. Every time we do a memory lookup, if it's in cache, it's (essentially) free, and if it's not in cache then we do some work to load that memory address - plus the contents of memory around that location - into cache. We then only care about how many times we have to load something into the cache, since that more accurately predicts the runtime.

In the case of a linked list, where cells can be scattered randomly throughout memory, we'd expect to do Θ(n) memory transfers when scanning a linked list, since we basically will never expect to have a linked list cell already in cache. However, with an array, every time we find an array element not in cache, we pull into cache all the adjacent memory locations, which then means the next few elements will definitely be in the cache. This means that only (roughly) every 1/B lookups will trigger a cache miss, so we expect to do Θ(n / B) memory transfers. This predicts theoretically what we see empirically - it's much faster to sequentially scan an array than a linked list.

So to summarize, this is really an issue of what you're measuring and how you measure it. If you just count memory accesses, both sequential accesses will require O(n) memory accesses and thus take O(n) time. However, if you just care about cache misses, then sequential access of a dynamic array requires Θ(n / B) transfers while a linked list scan requires Θ(n) transfers, which is why the linked list appears to be slower.

This sort of analysis is often used when designing data structures for databases. The B-tree (and its relative the B+-tree), which are used extensively in databases and file systems, are specifically tuned around the size of a disk page to reduce memory transfers. More recent work has been done to design "cache-oblivious" data structures that always take optimal advantage of the cache even without knowing its size.

Upvotes: 3

dspr
dspr

Reputation: 2423

Accessing the value at a certain index, let's say, 500, in an array is "immediate" (O(1)) while, with a linked list, you must iterate over 500 nodes to get the wanted one (O(n)).

Therefore, with an array, an indice at the beginning or at the end of the container is accessible at the same speed while with a linked list, more the index is high more it takes time to get it.

At the contrary, inserting a node in a linked list is easy and fast, while doing the same in an array is slower.

So the question becomes what is the more common operation : accessing indices (writing, reading) or manipulating the container structure (inserting, removing) ? The answer seems obvious but it could be some cases where it's not.

Upvotes: 0

davidbuzatto
davidbuzatto

Reputation: 9424

Unfortunatelly you missunderstood how these things work.

  • Sequencialy scan all array elements is O(n), being n the size of the array, since you will visit each element. You will need to calculate each address and the fetch the data n times;
  • Sequencialy scan all linked list elements is O(n), being n the size of the linked list, since you will visit each element throught the links;
  • Acessing one element of an array is O(1), since the access is related to one memory address calculation and one fetch process;
  • Acessing one element of an linked lisk is O(n), being n the position that you want to access, because you need to arrive on the nth element hopping each link until you reach the desired element.

Upvotes: 0

Related Questions