Search code examples
algorithmbig-ospace-complexity

What is the space complexity of duplicating the input?


I have some strings as input and I need to manipulate their individual characters, which I do more efficiently by first splitting the strings into arrays of characters. So in short, my algorithm is duplicating the input. What would be its space complexity?


Solution

  • The same space complexity as the original problem.

    If you have an input of n characters arranged in strings, that carries a spatial complexity of O(n). All you do is arrange them in some different way and duplicating the space you need: 2n and thus having a complexity of O(2n).

    However O(n) is equivalent to O(kn), being k any constant. Doesn't mean both problems consume the same memory but complexity wise they are equivalent.