An app stores many identifiers and checks whether each one has already appeared.
What You Need to Understand
Appending to a list is typically amortized O(1), but inserting at the beginning is O(n) because items shift. Searching for a value in a list is O(n) in the worst case; a set can provide faster average membership checks.
When to Use It
An app stores many identifiers and checks whether each one has already appeared.
Step-by-Step Python Example
numbers = []
for number in range(5):
numbers.append(number)
number_set = set(numbers)
print(4 in numbers)
print(4 in number_set)How the Example Works
Both membership checks return true. Performance differences become meaningful with large collections and repeated lookups.
Example Output
True
True
['Start', 'A', 'B']A Second Example
Compare this smaller variation with the main example, then experiment with your own values.
values = ["A", "B"]
values.insert(0, "Start")
print(values)Important Behavior and Edge Cases
Big-O describes how work scales rather than a guaranteed elapsed time. Avoid optimizing tiny programs before measuring real behavior.
Try It Yourself
Create a list and set of 1,000 integer IDs and compare repeated membership checks using timeit.
Common Beginner Mistakes
- Big-O describes how work scales rather than a guaranteed elapsed time. Avoid optimizing tiny programs before measuring real behavior.
- Overlooking how an iterable is consumed, how element positions are chosen, or whether a function creates a new list.
Key Takeaways
- Appending to a list is typically amortized O(1), but inserting at the beginning is O(n) because items shift.
- Both membership checks return true.
- Big-O describes how work scales rather than a guaranteed elapsed time.