Algorithmic Efficiency Hacks: Python

Let’s test your knowledge on algorithmic efficiency!

Hack 1: How Much Time?

Objective: write the time complexity of the algorithm below using Big-O notation.

(don’t worry about special cases such as n = 1 or n = 0).

n = int(input())  # remember what O(n) means? This is a good way of visualizing n.

for i in range(n):
    print(i)

# TODO: print the above algorithm's time complexity
print("Time complexity: O(n)")

---------------------------------------------------------------------------

ValueError                                Traceback (most recent call last)

Cell In[1], line 1
----> 1 n = int(input())  # remember what O(n) means? This is a good way of visualizing n.
      3 for i in range(n):
      4     print(i)


ValueError: invalid literal for int() with base 10: ''

Hack 2: Your Turn!

Objective: write an algorithm with O(n^2) time complexity.

n = int(input())

# TODO: Write an algorithm with O(n^2) time complexity
# Hint: think about nested loops...

for i in range(n):
    for j in range(n):
        print(i, j)

print("Time complexity: O(n^2)")

---------------------------------------------------------------------------

ValueError                                Traceback (most recent call last)

Cell In[2], line 1
----> 1 n = int(input())
      3 # TODO: Write an algorithm with O(n^2) time complexity
      4 # Hint: think about nested loops...
      6 for i in range(n):


ValueError: invalid literal for int() with base 10: ''

Hack 3: Gotta Go Fast!

Objective: Optimize this algorithm so that it has a lower time complexity without modifying the outer loop

import math
n = int(input())
count = 0

for i in range(n):
    count += math.ceil(math.sqrt(n) * 2)

print(count)

---------------------------------------------------------------------------

ValueError                                Traceback (most recent call last)

Cell In[4], line 2
      1 import math
----> 2 n = int(input())
      3 count = 0
      5 for i in range(n):


ValueError: invalid literal for int() with base 10: ''

Hack 4: Extra Challenge

Objective: Write an algorithm that does NOT have a time complexity of O(1), O(n), or O(n^x) and identify the time complexity

(I will not accept O(n^3) or some other power, it needs to be more complex.)
import math

n = int(input())

count = 0

for i in range(n):
    j = 1
    while j < n:
        count += 1
        j *= 2  # doubles each time

print(count)
print("Time complexity: O(n log n)")

---------------------------------------------------------------------------

ValueError                                Traceback (most recent call last)

Cell In[1], line 3
      1 import math
----> 3 n = int(input())
      5 count = 0
      7 for i in range(n):


ValueError: invalid literal for int() with base 10: ''