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