Practical Examples

Here’s some typical Python code that prints all the items from a list:

	things = ['apples', 'baboons', 'cribs', 'dulcimers']

	for thing in things:
	print("Here's a thing: " + thing)

How would we describe the efficiency of this algorithm in Big O notation?

The first thing to realize is that this is an example of an algorithm. While it may not be fancy, any code that does anything at all is technically an algorithm—it’s a particular process for solving a problem. In this case, the problem is that we want to print all the items from a list. The algorithm we use to solve this problem is a for loop containing a print statement.

To break this down, we need to analyze how many steps this algorithm takes. In this case, the main part of the algorithm—the for loop—takes four steps. In this example, there are four things in the list, and we print each one out a single time.

However, the number of steps isn’t constant. If the list contained ten elements, the for loop would take ten steps. Since this for loop takes as many steps as there are elements, we’d say that this algorithm has an efficiency of O(N).

The next example is a simple Python-based algorithm for determining whether a number is prime:

	def is_prime(number):
	for i in range(2, number):
	if number % i == 0:
	return False

	return True

The preceding code accepts a number as an argument and begins a for loop in which we divide the number by every integer from 2 up to (but not including) that number and see if there’s a remainder. If there’s no remainder, we know that the number is not prime and we immediately return False. If we make it all the way up to the number and always find a remainder, then we know that the number is prime and we return True.

In this case, the key question is slightly different than in the previous examples. In the previous examples, our key question asked how many steps the algorithm would take if there were N data elements in an array. Here, we’re not dealing with an array, but we are dealing with a number that we pass into this function. Depending on the number we pass in, this will affect how many times the function’s loop runs.

In this case, then, our key question will be: when passing in the number N, how many steps will the algorithm take?

If we pass the number 7 into is_prime, the for loop runs about 7 times. (It technically runs 5 times, since it starts at 2 and ends right before the actual number.) For the number 101, the loop runs about 101 times. Because the number of steps increases in lockstep with the number passed into the function, this is a classic example of O(N).

Again, the key question here dealt with a different kind of N, since our primary piece of data was a number rather than an array. We’ll get more practice in identifying our Ns as we progress through the future chapters.