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

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

print("O(n)")

#TODO: print the above algorithm's time complexity

0
1
2
3
4
5
6
7
8
9
O(n)

Hack 2: Your Turn!

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

n = int(input())


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

print("O(n^2)")

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

0 0
0 1
0 2
0 3
0 4
1 0
1 1
1 2
1 3
1 4
2 0
2 1
2 2
2 3
2 4
3 0
3 1
3 2
3 3
3 4
4 0
4 1
4 2
4 3
4 4
O(n^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

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

print(count)
print("O(n)")

#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?

25
O(n)

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.)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

n = int(input())
print(f"Fibonacci({n}) =", fibonacci(n))

# ✅ Time Complexity:
print("O(2^n)")

#TODO: Write an algorithm that has a more complicated time complexity than O(n^x).

Fibonacci(15) = 610
O(2^n)