patternModerate
Algorithms with O(sqrt(N)) SPACE complexity?
Viewed 0 times
spacewithalgorithmssqrtcomplexity
Problem
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.
Solution
$\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.
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.
Context
StackExchange Computer Science Q#68303, answer score: 15
Revisions (0)
No revisions yet.