What is gradient checkpoint recomputation cost complexity?

Checkpointing reduces memory from O(n) to O(√n) at the cost of recomputing forward passes.

Instead of storing all activations, only selected checkpoints are stored. During backward pass, missing activations are recomputed, increasing compute cost but significantly reducing memory footprint.