title: Time complexity of sequentially scanning an array vs a linked list?
body: <p>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?</p>
  <p>For scanning array, does perfoming <em>n</em> * random accesses i.e. O(1) operations mean that overall it becomes O(n)? In that case wouldn't both be O(n)?</p>
  <p>Sorry if this question doesn't make sense, maybe my understanding of time complexities isn't so good.</p>