Exercises

The following exercises provide you with the opportunity to practice analyzing algorithms. The solutions to these exercises are found in the section .

1. Use Big O notation to describe the time complexity of an algorithm that takes 4N + 16 steps.

2. Use Big O notation to describe the time complexity of an algorithm that takes 2N².

3. Use Big O notation to describe the time complexity of the following function, which returns the sum of all numbers of an array after the numbers have been doubled:

   ​	​def​ ​double_then_sum​(array):
   ​	doubled_array = []
   ​
   ​	​for​ number ​in​ array:
   ​	doubled_array.append(number * 2)
   ​
   ​	sum = 0
   ​
   ​	​for​ number ​in​ doubled_array:
   ​	sum += number
   ​
   ​	​return​ sum

4. Use Big O notation to describe the time complexity of the following function, which accepts an array of strings and prints each string in multiple cases:

   ​	​def​ ​multiple_cases​(array):
   ​	​for​ string ​in​ array:
   ​	​print​(string.upper())
   ​	​print​(string.lower())
   ​	​print​(string.capitalize())

5. The next function iterates over an array of numbers. As it does so, it focuses on every other number while ignoring the numbers in between. For each “focus number,” the function proceeds to print out every number from the array—one at a time—after being added to the focus number.

   What is this function’s efficiency in terms of Big O notation?

   ​	​def​ ​every_other​(array):
   ​	​for​ index, number ​in​ enumerate(array):
   ​	​if​ index % 2 == 0:
   ​	​for​ other_number ​in​ array:
   ​	​print​(number + other_number)