Exercises

The following exercises provide you with the opportunity to practice with Big O notation. The solutions to these exercises are found in the section .

Use Big O notation to describe the time complexity of the following function that determines whether a given year is a leap year:

	def is_leap_year(year):

	if year % 100 == 0:
	if year % 400 == 0:
	return False
	else:
	return True

	return year % 4 == 0

Use Big O notation to describe the time complexity of the following function that sums up all the numbers from a given array:
def array_sum(array):
sum = 0

for number in array:
sum += number

return sum

The following function is based on the age-old analogy used to describe the power of compounding interest:

Imagine you have a chessboard, and put a single grain of rice on one square. On the second square, you put two grains of rice, since that is double the amount of rice on the previous square. On the third square, you put four grains. On the fourth square, you put eight grains, and on the fifth square, you put sixteen grains, and so on.

The following function calculates which square you’ll need to place a certain number of rice grains. For example, for sixteen grains, the function will return 5, since you will place the sixteen grains on the fifth square.

Use Big O notation to describe the time complexity of this function, which is below:

	def chessboard_space(number_of_grains):
	chessboard_spaces = 1
	placed_grains = 1

	while placed_grains < number_of_grains:
	placed_grains *= 2
	chessboard_spaces += 1

	return chessboard_spaces

The following function accepts an array of strings and returns a new array that only contains the strings that start with the character "a". Use Big O notation to describe the time complexity of the function:

	def select_a_strings(array):
	new_array = []

	for string in array:
	if string[0] == "a":
	new_array.append(string)

	return new_array

The following function calculates the median from an ordered array. Describe its time complexity in terms of Big O notation:

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

	middle = len(array) // 2

	# If array has even amount of numbers:
	if len(array) % 2 == 0:
	return (array[middle - 1] + array[middle]) / 2.0
	else: # If array has odd amount of numbers:
	return array[middle]

	def array_sum(array):
	sum = 0

	for number in array:
	sum += number

	return sum