Concepts13
Complexity Analysis Quick Reference
Use an operation budget of about 10^8 simple operations per second on typical online judges; always multiply by the time limit and number of test files if known.
Small-to-Large Principle
Small-to-large means always merge the smaller container into the larger one to keep total work low.
Double Counting
Double counting is the strategy of counting the same quantity in two different ways to derive an equality or an efficient algorithm.
Think Backwards (Reverse Thinking)
Think Backwards is a problem‑solving pattern where you reverse time or direction so hard deletions become easy insertions and the final state becomes the starting point.
Invariant Maintenance
An invariant is a property you promise to keep true throughout an algorithm, and it is the anchor of both design and correctness proofs.
Amortized Analysis
Amortized analysis measures the average cost per operation over a worst-case sequence, not over random inputs.
Small-to-Large Merging
Small-to-large merging is a technique where you always merge the smaller container into the larger one to guarantee low total work.
Minimum Rotation
The minimum rotation of a string is the lexicographically smallest string you can get by cutting it at some position and swapping the two parts.
Sliding Window
Sliding window is a technique that moves a contiguous segment (window) across an array or string while maintaining some running information like sum, count, or max.
Disjoint Set Union (Union-Find)
Disjoint Set Union (Union-Find) maintains a collection of non-overlapping sets and supports fast merging and membership queries.
Queue and Deque
A queue is a First-In-First-Out (FIFO) line where you add at the back and remove from the front in O(1) time.
Monotonic Deque
A monotonic deque is a double-ended queue that keeps elements in increasing or decreasing order so that the front always holds the current optimum (min or max).