'When a problem in data structures mentions to solve it in O(n) space complexity, does it mean that I can use only one external data structure or more?
I have a very basic question. When a problem in data structures mentions to solve it in O(n) space complexity, does it mean that I can use only one external data structure or more? As an example, if an array problem mentions to solve it in O(n) space complexity, does that mean that I can use only one array ? or I can use more than one array ?
Solution 1:[1]
You can use as many data structures as you want, so long as their combined size is within O(n). If there are a fixed number of such data structures and each one is in O(n) then the total will also be within O(n).
Loops have to do with CPU complexity, not Space complexity.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | RBarryYoung |