1. Complexity Analysis

Key Insight

Big-O describes how runtime or memory scales as input grows — not absolute speed. Always analyze the worst case unless told otherwise. In CP, $10^8$ simple operations ≈ 1 second; use this to choose the right algorithm tier.

Big-O Cheat Sheet

Complexity	Name	Max $n$ in 1s	Example
$O(1)$	Constant	Any	Hash lookup
$O(\log n)$	Logarithmic	$10^{18}$	Binary search
$O(n)$	Linear	$10^8$	Single loop
$O(n \log n)$	Linearithmic	$10^6$	Merge sort
$O(n^2)$	Quadratic	$10^4$	Nested loop
$O(n^3)$	Cubic	$500$	3-loop DP
$O(2^n)$	Exponential	$20\text{–}25$	Subset enumeration
$O(n!)$	Factorial	$12$	Permutations

Python-Specific Gotchas

# list.append / list.pop(-1)  → O(1) amortized
# list.insert(0, x) / list.pop(0) → O(n) — use collections.deque instead
# dict / set lookup, insert, delete → O(1) average, O(n) worst (hash collision)
# sorted() / list.sort() → O(n log n) — Timsort
# "".join(list_of_str) → O(n); repeated += on str → O(n²) — always use join
# in operator on list → O(n); on set/dict → O(1)

import sys
# Recursion limit — increase for deep DFS
sys.setrecursionlimit(300_000)

# Fast I/O for CP
input = sys.stdin.readline

Amortized Analysis

• list.append is $O(1)$ amortized: occasional $O(n)$ resize is spread over $n$ appends.
• dict inserts are $O(1)$ amortized but can degrade with poor hash functions (rare in Python).

Space Complexity

• Always track auxiliary space separately from input space.
• Recursion depth = $O(n)$ stack space for DFS on a skewed tree.

---