# Algorithms with O(sqrt(N)) SPACE complexity?

Are there any known algorithms for formulated problems that require a SPACE complexity of O(sqrt(N))? I know that algorithms with that big-O time complexity exist.

• For an important problem called 3sum, there is the following trade-off. If you want $O(n^2)$ time, the best-known space complexity is $O(\sqrt{n})$. See arxiv.org/abs/1605.07285
– eig
Jan 12 '17 at 19:55

$\sqrt{n}$ space is somewhat unusual; the most likely reason for such a complexity to emerge is as a result of a so-called meet in the middle scheme.