Codzy

Time and space complexity

Complexity measures how an algorithm's time (or memory) grows as the data gets bigger. It's written with Big O notation: O(1) constant, O(log n) like binary search, O(n) a simple loop, O(n²) two nested loops.

Space complexity measures the memory used. You often trade a little memory for a lot of speed: searching a list is O(n), but searching a set or a dict is O(1) on average.

def count_steps(n):
    steps = 0
    for i in range(n):
        for j in range(n):
            steps += 1
    return steps

for n in [10, 20, 40]:
    print(n, "->", count_steps(n), "steps")

names = set(["Ana", "Ben", "Chloe"])
print("Ben" in names)

Start the lesson