🧠 Complexity + Memory Model

Why it matters

Speed and space are what separate accepted from TLE solutions.

The idea

Think in operations per input size. list.append() is O(1) amortised; list.insert(0, x) is O(n) because everything shifts. set / dict lookup is O(1); list membership (x in lst) is O(n).

See O(n²) in action

Bubble sort compares every adjacent pair and bubbles the largest to the end on each pass. Tap Auto and count: 24 elements take ~200 comparisons. Doubling to 48 wouldn't take 2× — it would take ~4×. That's what O(n²) looks like.

Try it

Time the difference between list and set membership:

import time

N = 50000
data = list(range(N))
data_set = set(data)
needles = [N - 1, N // 2, 0]

t0 = time.perf_counter()
hits_list = sum(1 for x in needles if x in data)
t1 = time.perf_counter()
hits_set = sum(1 for x in needles if x in data_set)
t2 = time.perf_counter()

print(f"list lookups: {hits_list}  time: {(t1-t0)*1e6:.1f} µs")
print(f"set  lookups: {hits_set}  time: {(t2-t1)*1e6:.1f} µs")

Shallow vs deep copy — mutables surprise people:

import copy

grid = [[0] * 3 for _ in range(3)]
shallow = list(grid)       # same inner lists!
deep = copy.deepcopy(grid)

shallow[0][0] = 99
deep[0][0] = -1

print("grid    :", grid)
print("shallow :", shallow)
print("deep    :", deep)

In place mutation vs new object:

# sorted() makes a new list, sort() mutates in place
nums = [3, 1, 4, 1, 5]
asc = sorted(nums)         # new
nums.sort(reverse=True)    # in place
print("asc :", asc)
print("nums:", nums)

Quick check

• Q: Which is faster for membership: list or set? A: set.

Mini drills

• Identify which types are mutable.
• Explain why b = a can be dangerous.

Common mistakes

• Mistake: Assuming b = a copies data. Fix: Use a.copy() or list(a).
• Mistake: Mutating an input inside a function unintentionally. Fix: Document it, or copy first.

Key takeaways

• list.append() O(1) amortised; list.insert(0, x) O(n).
• x in set / x in dict is O(1); x in list is O(n).
• list(other) is a SHALLOW copy — inner mutables are still shared.
• copy.deepcopy is correct but slow; only use when you need full isolation.