Iterative naive (d-Neighborhood of a String d-Neighborhood of a String)
Jump to navigation
Jump to search
Time Complexity
$O(f_{bin}(sigma-{1}, n, d)$) where f_{bin}(x, y, z) = sum_{i=0}^z C(y, i)*x^i
Space Complexity
$O(n)$ words
(Keep track of which indices the differing letters are on, along with which set of letters are replacing the letters in these indices)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
1940