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