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)")

Hack 2: Your Turn!

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

# O(n^2) time complexity
n = int(input())

for i in range(n):           # Outer loop runs n times
    for j in range(n):       # Inner loop runs n times for each outer loop
        print(i, j)

# Time complexity: O(n^2)
# Explanation: Outer loop = O(n), Inner loop = O(n), total = O(n * n) = O(n^2)
#TODO: Write an algorithm with O(n^2) time complexity
#Hint: think about nested loops...

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

ValueError                                Traceback (most recent call last)

Cell In[1], line 2
      1 # O(n^2) time complexity
----> 2 n = int(input())
      4 for i in range(n):           # Outer loop runs n times
      5     for j in range(n):       # Inner loop runs n times for each outer loop


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

n = int(input())
count = 0

for i in range(n):       # keep the outer loop the same
    # Instead of running another inner loop, just add the number of steps directly
    count += i

print(count)

# Time complexity: O(n)
# Originally O(n^2) because of the inner loop
# Now O(n) because the inner loop is replaced with a single operation

#TODO: make this algorithm more efficient, but keep the outer loop and make sure the output is still the same!
#Hint: how does the inner loop affect time complexity?

42

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.)
n = int(input())

def fib(x):
    if x <= 1:
        return x
    return fib(x - 1) + fib(x - 2)

print(fib(n))

# Time complexity: O(2^n)
# Explanation:
# Each call to fib makes 2 more calls (except the base case),
# so the number of calls grows exponentially with n.
# This is more complex than O(n^x) and valid for this challenge.
#TODO: Write an algorithm that has a more complicated time complexity than O(n^x).