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’s an implementation of this function. See if you can identify its efficiency in Big O:

	def sample(array):
	if not array:
	return None

	first = array[0]
	middle = array[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 matter the size of the array. Similarly, finding the array’s length and dividing it by 2 also takes one step.

Since the number of steps is constant—that is, it remains the same no matter what N is—this algorithm is considered O(1).