O(n²)

Python · Unit 22: Complexity

Comparing everyone against everyone is a loop inside another over the same list: n times n steps.

That label is O(n²), and it grows ugly: with 10 names it is 100 steps, with 100 names it is already 10,000.

def pairs(names):
    steps = 0
    for a in names:
        for b in names:
            steps += 1
    return steps

print(pairs(["Ana", "Luke"]))

Prints

The rest of the explanation is in the lesson, which is part of the full plan.

Exercises in this lesson

You do them in the app, which checks them on the spot and explains why.

1. Predict the output
What does this code print?
2. Multiple choice
An O(n²) function makes 10,000 steps with n = 100. How many will it make with n = 200?
3. Predict the output
What does this code print?
4. Complete the code
Complete it so each pair is counted a single time.
5. Find the bug
It should say how many pairs of equal numbers the list holds, that is 1. Which line has the error?
6. Predict the output
What does this code print?
7. Put the lines in order
Put together an O(n²) function that says whether some number repeats, comparing every pair.
8. Multiple choice
Both count how many different numbers there are. Which label does each one get?

It opens in your browser. This lesson is part of the full plan; the first unit of each course is free.