square root decomposition

English

Alternative forms

sqrt decomposition

Noun

square root decomposition (plural square root decompositions)

(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.

This article is issued from Wiktionary. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.