A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Array Sample

In the next example, we create a function that takes a small sample of an array. We expect to have very large arrays, so our sample is just the first, middlemost, and last value from the array.

Here is a Python implementation of this function. See if you can identify its efficiency in Big O:

def sample(array):
  first = array[0]
  middle = array[int(len(array) / 2)]
  last = array[-1]

  return [first, middle, last]

In this case again, the array passed into this function is the primary data, so we can say that N is the number of elements in this array.

However, our function ends up taking the same number of steps no matter what N is. Reading from the beginning, midpoint, and last indexes of an array each takes one step no ...