1
$\begingroup$

In the problem find-all-anagrams-in-a-string, one tries to find all anagrams of a string $p$ (of length $k$) in a string $s$ (of length $n$) and return a list of the anagrams' starting indices.

The solution is to use a sliding window of length $k$ and move that window from the first index all the way up index $n - k + 1$. However, the solution states that the space complexity is $O(1)$ instead of $O(n)$. This is confusing to me, as shouldn't it be $O(n)$ as the worst case scenario is that $p$ is 1 character and $s$ (with length $n$) is comprised solely of $p$'s character? Then the start indices list we would return would be of length $n$.

$\endgroup$
3
  • 5
    $\begingroup$ You say "space complexity" in the title and "time complexity" in your question. Which is it that interests you? Obviously, the solution must take at least O(n) time, but the amount of auxiliary space (other than the result vector) could be O(1). It's reasonable to exclude the result vector because the algorithm could return the indices one at a time; there's no need to collect them. $\endgroup$
    – rici
    Commented Sep 22, 2021 at 1:07
  • $\begingroup$ @rici The question asks to return a list of all the starting indices of anagrams, and it is the space complexity that interests me :D $\endgroup$
    – Adam Lee
    Commented Sep 22, 2021 at 21:14
  • $\begingroup$ There are different definitions of what space to account for. $O(1)$ reads excluding input and output. $\endgroup$
    – greybeard
    Commented Sep 23, 2021 at 20:35

1 Answer 1

1
$\begingroup$

No, because you can write an algorithm with space complexity $O(1)$ that prints an unlimited amount of output. For instance, here is one

while true:
    print('yo!')

This means that the length of the output can be much larger than the space complexity, and the length of the output is not a lower bound on the space complexity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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