How does the choice of data structure change a program's performance?

Short answer

The time complexity of the basic operations determines performance more than any other optimization: a membership check in a set or dict averages O(1), while in a list it is linear O(n), and this difference grows with data size.

Explanation

Analyze the dominant operations before choosing: repeated lookups mean set or dict, both ends mean deque, always needing the smallest element means heapq, and searching a sorted list means bisect. But set and dict use more memory and need hashable keys, and the O(1) value is an average, not a guarantee. The decision is always a trade-off between time, memory, and ordering, and is confirmed by measurement.

Code example

banned = load_banned_ids()           # 100k Item
banned_set = set(banned)

# O(n * m)
valid = [u for u in users if u.id not in banned]
# O(n)
valid = [u for u in users if u.id not in banned_set]

import bisect
scores = sorted(all_scores)
rank = bisect.bisect_left(scores, 75)  # O(log n)

Common mistakes

• Searching inside a list in a loop over large data.
• Assuming O(1) means constant speed no matter how bad the hash function is.

Follow-up questions

• When should you choose a list, tuple, set or dict?
• When do you use collections.deque instead of list?

Sources

• Python Wiki — TimeComplexity