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("O(n)")

0
1
2
O(n)

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
for i in range(n):
    for j in range(n):
        print(i, j)

# Hint: think about nested loops...

0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

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

# Pre-calculate how many times the inner loop would run
inner_iterations = math.ceil(math.sqrt(n) * 2)

for i in range(n):
    count += inner_iterations  # adds the same amount each time

print(count)

12

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 generate_subsets(nums):
    if not nums:
        return [[]]
    first = nums[0]
    rest = generate_subsets(nums[1:])
    return rest + [[first] + subset for subset in rest]

# create a list of size n
nums = list(range(n))
subsets = generate_subsets(nums)

print(f"Generated {len(subsets)} subsets.")
print("Time complexity: O(2^n)")

Generated 8 subsets.
Time complexity: O(2^n)