13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – eig Jan 12 '17 at 19:55
15
$\begingroup$

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

Two notable examples off the top of my head are the classical sieve of Eratosthenes and the baby-step giant-step algorithm for the discrete logarithm over a finite group.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.