# Why is the space complexity of finding anagrams in a string O(1) instead of O(n)?

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

• 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.
– rici
Commented Sep 22, 2021 at 1:07
• @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 Commented Sep 22, 2021 at 21:14
• There are different definitions of what space to account for. $O(1)$ reads excluding input and output. Commented Sep 23, 2021 at 20:35

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: