square root decomposition

Noun

• A technique that can reduce the runtime of an algorithm by a factor of $\backslash sqrt\{n\}$ (where $n$ is the size of the input) by dividing the input into $\backslash sqrt\{n\}$ chunks and performing operations on whole chunks when possible.