square root decomposition

English

Alternative forms

• sqrt decomposition

Noun

square root decomposition (plural square root decompositions)

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