·5 min read
Python for DSA — Time & Space Complexity
PythonDsaComplexityBig-oTime-complexitySpace-complexity
10. Time & Space Complexity (Python-specific)
💡 Why this matters for DSA Understanding the actual cost of Python operations prevents surprising TLE (Time Limit Exceeded) errors. Not all O(1) operations are equal, and some Python "one-liners" hide O(n) or O(n²) costs.
10.1 Python Operation Costs
Lists
| Operation | Cost | Notes |
|---|---|---|
Index / Assign arr[i] | O(1) | |
Append arr.append(x) | O(1) | Amortized |
Pop (end) arr.pop() | O(1) | |
Pop (index) arr.pop(i) | O(n) | Shifts elements |
Insert arr.insert(i, x) | O(n) | Shifts elements |
Remove arr.remove(x) | O(n) | Search + shift |
Slice arr[i:j] | O(k) | Creates new list of k elements |
x in arr | O(n) | Linear search |
arr.sort() | O(n log n) | Timsort (fast on partially sorted) |
len(arr) | O(1) | Stored as attribute |
Copy arr.copy() / arr[:] | O(n) |
Dicts & Sets
| Operation | Cost | Notes |
|---|---|---|
d[key] / key in d | O(1) | Average case |
d[key] = val | O(1) | Average case |
d.pop(key) | O(1) | Average case |
s.add(x) | O(1) | Average case |
x in s | O(1) | ⭐ This is why sets exist |
| Iteration | O(n) |
⚠️ Warning — O(1) is amortized average: In rare cases (hash collision, rehashing), a single operation can be O(n). But for DSA problems, treat dict/set operations as O(1).
Strings
| Operation | Cost | Notes |
|---|---|---|
Index s[i] | O(1) | |
Slice s[i:j] | O(k) | Creates new string |
Concatenate s + t | O(n+m) | |
x in s | O(n) | |
.join(list) | O(n) | ✅ Preferred over + in loops |
s.split() | O(n) |
10.2 Hidden Costs That Bite You
❌ String concatenation in a loop
python
# BAD — O(n²)
s = ""
for ch in ["a", "b", "c", ... 100_000]:
s += ch # creates new string each time!
# GOOD — O(n)
chars = []
for ch in huge_list:
chars.append(ch)
s = "".join(chars)
❌ list.pop(0) or list.insert(0, x)
python
# BAD — O(n²) for n operations
queue = []
queue.append(1)
queue.pop(0) # O(n)!
# GOOD — O(1) per operation
from collections import deque
queue = deque()
queue.append(1)
queue.popleft() # O(1)
❌ x in list in a loop
python
# BAD — O(n²)
for x in big_list:
if x in another_big_list: # O(n) each time
...
# GOOD — O(n) total
big_set = set(another_big_list)
for x in big_list:
if x in big_set: # O(1) each time
...
❌ Repeated del arr[0]
python
# BAD — O(n²)
while arr:
x = arr.pop(0) # shifts entire list each time
# GOOD — use index or deque
i = 0
while i < len(arr):
x = arr[i]
i += 1
10.3 Choosing the Right Data Structure
| You need... | Use... | Why |
|---|---|---|
| Fast lookups by value | set | O(1) membership |
| Key-value mapping | dict | O(1) get/set |
| Stack (LIFO) | list | O(1) append/pop (end) |
| Queue (FIFO) | deque | O(1) append/popleft |
| Priority queue | heapq | O(log n) push/pop |
| Count frequencies | Counter | Built-in .most_common() |
| Group items by key | defaultdict(list) | Auto-initialize |
| Sorted data | list + .sort() | Timsort O(n log n) |
| Unique ordered items | dict (Python 3.7+) | Insertion order preserved |
Quick decision flow
Need to check if item exists? → Set (O(1))
Need to count things? → Counter / dict
Need to process in order? → deque (queue) / list (stack)
Need the smallest/largest always? → heapq
Need fast lookups by key? → dict
Need to group items? → defaultdict(list)
10.4 Complexity Cheat Sheet for DSA
O(1) — Constant
- Dict/set lookup, assignment
- List index, append, pop (end)
len(),min(),max()on small fixed data
O(n) — Linear
- Iterating over a list/set/dict
x in list(worst case)- String/List slicing
list.copy(),list.count()
O(n log n) — Linearithmic
- Sorting (
sorted(),.sort()) - Heap operations (per element)
O(n²) — Quadratic ⚠️
- Nested loops over same data
list.pop(0)in a loop- Naive string concatenation in a loop
✅ Tip — Rule of thumb for constraints:
n Acceptable complexity n ≤ 100 O(n²) or even O(n³) n ≤ 10⁴ O(n²) risky, O(n log n) safe n ≤ 10⁵ O(n log n) or O(n) n ≤ 10⁶ O(n) or O(n log n) n ≤ 10⁷+ O(n) with efficient code
Practice Drill
python
# 1. What's the time complexity of this?
def fn(arr):
result = []
for x in arr:
result.insert(0, x) # ???
return result
# 2. What's wrong with this string building?
s = ""
for i in range(100000):
s += str(i)
# 3. Why use deque instead of list for BFS?
💡 Click for Solutions
python
# 1. O(n²) — insert(0, x) at front shifts all elements each time
# Fix: use .append() and reverse at end, or use deque.appendleft()
# 2. O(n²) — each s += str(i) creates a new string
# Fix: use a list and .join()
# 3. BFS needs popleft() — list.pop(0) is O(n), deque.popleft() is O(1)
# For a graph with V vertices and E edges, using list.pop(0) makes BFS O(V²)