Structures and performance

Python · Unit 22: Complexity

x in list looks one by one: in the worst case it walks the whole list, O(n).

x in set walks nothing, because the value itself tells Python where to look: O(1). The same goes for the keys of a dictionary.

names = ["Ana", "Luke", "Mia"]
friends = set(names)
print("Luke" in names)
print("Luke" in friends)

Prints

True
True

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
The counter says how many numbers had to be looked at to find the 7. What does it print?
2. Multiple choice
team is a list with 1000 names and members is a set with those same names. What is the difference between x in team and x in members?
3. Predict the output
What does this code print?
4. Complete the code
Complete it to leave the members ready to be searched many times.
5. Put the lines in order
Put together a function that counts how many of the numbers are in the seen set.
6. Find the bug
It should say how many different names there are, that is 2. Which line has the error?
7. Predict the output
Remember that fib(5) cost 15 calls. How many does fib(10) cost?
8. Multiple choice
Every challenge in the app carries a label: O(1), O(log n), O(n), O(n log n), O(n²) or O(2ⁿ). What does that label tell you?

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