Square root decomposition

English

Alternative forms

• Template:Alter

Noun

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