Average Celsius Reading

Here’s another example that involves mean averages. Let’s say we’re building weather-forecasting software. To determine the temperature of a city, we take temperature readings from many thermometers across the city, and we calculate the mean average of those temperatures.

We’d also like to display the temperatures in both Fahrenheit and Celsius, but our readings are initially only provided to us in Fahrenheit.

To get the average Celsius temperature, our algorithm does two things: first, it converts all the readings from Fahrenheit to Celsius. Then it calculates the mean average of all the Celsius numbers.

Below is some code that accomplishes this. What is its Big O?

	def average_celsius(fahrenheit_readings):
	if not fahrenheit_readings:
	return None

	celsius_numbers = []

	# Convert each reading to Celsius and append to array:
	for fahrenheit_reading in fahrenheit_readings:
	celsius_conversion = (fahrenheit_reading - 32) / 1.8
	celsius_numbers.append(celsius_conversion)

	# Calculate average:
	sum = 0

	for celsius_number in celsius_numbers:
	sum += celsius_number

	return sum // len(celsius_numbers)

First, we can say that N is the number of fahrenheit_readings passed into our method.

Inside the method, we run two loops. The first converts the readings to Celsius, and the second sums all the Celsius numbers. Since we have two loops that each iterate over all N elements, we have N + N, which is 2N (plus a few constant steps). Because Big O notation drops the constants, this gets reduced to O(N).

Don’t get thrown off by the fact that in the earlier word builder example, two loops led to an efficiency of O(N²). There, the loops were nested, which led to N steps multiplied by N steps. In our case, however, we simply have two loops, one after the other. This is N steps plus N steps (2N), which is a mere O(N).