Refactoring: Complexity Analysis Checklist

☐ Input size matches algorithm

N = 2×10⁵ with O(N²) → TLE. Check N, check your loops.

☐ 64-bit overflow?

Sum of N=10⁵ values up to 10⁹ → 10¹⁴ fits in 64-bit. But multiplication needs 128-bit or modular.

☐ Memory limit

int = 4 bytes. long long = 8 bytes. 10⁷ ints = 40 MB. Check your 2D arrays.

☐ Recursion depth

DFS on a chain of 10⁵ nodes → stack overflow. Use iterative or increase stack limit.

☐ Initialise variables

Uninitialised = UB in C++. Always initialise or use vector constructors.

☐ Test edge cases

N=1, N=max, all equal, already sorted, reversed, empty input (if allowed).