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 ${\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.