Python Big-O: Time & Space Complexity

Standard Library Complexity¶

The Python standard library provides highly optimized data structures and algorithms for common tasks.

Core Collections¶

• Collections - deque, namedtuple, defaultdict, OrderedDict, ChainMap, Counter
• Itertools - Efficient looping tools and iterators
• Heapq - Heap queue operations
• Bisect - Binary search and insertion

Functional & Utilities¶

• Functools - Higher-order functions and memoization
• JSON - JSON serialization and parsing

Search & Sort¶

Frequently Used¶

Collections Module¶

from collections import deque, defaultdict, Counter

# deque: Fast append/prepend
d = deque([1, 2, 3])
d.appendleft(0)  # O(1)

# defaultdict: Auto-default values
d = defaultdict(list)
d[key].append(value)  # Key created if missing

# Counter: Count items
c = Counter(['a', 'a', 'b'])
c['a']  # Returns 2

Heapq Module¶

import heapq

# Min heap operations
heap = [3, 1, 4, 1, 5]
heapq.heapify(heap)  # O(n)
heapq.heappop(heap)  # O(log n)
heapq.heappush(heap, 2)  # O(log n)

Bisect Module¶

import bisect

# Binary search in sorted lists
arr = [1, 3, 3, 3, 5]
bisect.bisect_left(arr, 3)  # O(log n)
bisect.insort(arr, 4)  # O(n) - must shift

Data Structure Quick Reference¶

Version Highlights¶

• Python 3.7+: dict insertion order preserved
• Python 3.8+: Assignment expressions (walrus operator)
• Python 3.10+: Pattern matching with dataclasses

See Also¶

• Built-in Types
• Implementations