0
$\begingroup$

I have some difficulties with understanding the space complexity of the following algorithm. I've solved this problem subsets on leetcode. I understand why solutions' space complexity would be O(N * 2^N), where N - the length of the initial vector. In all those cases all the subsets (vectors) are passed by value, so we contain every subset in the recursion stack. But i passed everything by reference. This is my code:

class Solution {
public:
vector<vector<int>> result;
void rec(vector<int>& nums, int &position, vector<int> &currentSubset) {
    if (position == nums.size()) {
        result.push_back(currentSubset);
        return;
    }
    
    currentSubset.push_back(nums[position]);
    position++;
    rec(nums, position, currentSubset);
    currentSubset.pop_back();
    rec(nums, position, currentSubset);
    position--;
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector <int> currentSubset;
    int position = 0;
    rec(nums, position, currentSubset);
    return result;
}
};

Would the space complexity be O(N)? As far as i know, passing by reference doesn't allocate new memory, so every possible subset would be contained in the same vector, which was created before the recursion calls.

I would also appreciate, if you told me how to estimate the space complexity, when working with references in general. Those are the only cases, where i hesitate about the correctness of my reasonings.

Thank you.

$\endgroup$
  • $\begingroup$ we contain every subset in the recursion stack at one single point in time? $\endgroup$ – greybeard Jul 3 at 5:39
  • $\begingroup$ @greybeard, yeah, as soon as new recursion call is made, new stack frame is allocated and a new subset is stored here. So we can say "at every single point of time" $\endgroup$ – Никита Бабенко Jul 3 at 10:25
1
$\begingroup$

All the computations of complexity depend on your model of computation, in other words on what you would like to count.

You may, as you say, only count memory that your code itself allocates. You should be aware that this way of counting space used can become useless easily. You can modify any algorithm to delegate all allocation to the caller. It is not very informative to say that you can solve any problem in constant space.

Another possibility is to count all memory space that gets accessed. If an algorithm accesses all the memory to store the input, do we count it? Some people do.

A more common way to define memory complexity is to measure the memory that the program modifies. Whether the program allocates it or the caller does, it doesn't matter in this case.

Relevant to the computation is also the units in which the memory is measured. You could count bits. This assumption leads to the claim that storing an integer $n$ will require $O(\log(n))$ of space. But this is not the only model used. You could assume that your model of a computer stores integers. In this model storing an integer requires just one unit of space. This is common when the size of the integers involved at not going to be large compared to other sizes of the inputs. These assumptions are relevant to the discussion in the comments. You both are right, but are using different units to quantify memory. These are not even the only options. Some models assume that a unit of memory can store an infinite precision real number, for example.

There are other aspects that sometimes are also taken into account. For example, in real world computers not all memory is the same. In some models memory is separated in a hierarchy. For example, according to response time. Registers and cache are faster than hard drive or magnetic tape. The space complexity can take into account how much of the different types of memory is used.

It is very common to just mention an $O$ class to which the amount of space used, as a function of some size of the input, belongs. To not be wrong it is better to clarify what is being counted and in what units.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ i'm used to measuring the space complexity in units of space. It doesn't matter whether it's an integer, char, etc. Therefore, one single variable would take O(1) memory to store and integer n, for example. Consequently, the array of size N would take O(N) memory. In the analysis of my code complexity and question i based on such metrics. For some more clarification, i need help in estimation the space complexity of passing the vector by reference in the recursion. $\endgroup$ – Никита Бабенко Jul 3 at 10:38
  • $\begingroup$ @НикитаБабенко The vector nums is not modified. You may count it, but commonly people don't. The integer position is modified. That counts as 1. The vector currentSubset is also modified and its largest size is the size $n$ of nums. Then you have the vector result, which contains all the subsets. Its size is the sum of the sizes of all subsets of nums. That gives $\sum_{k=1}^{n}k\binom{n}{k}=n2^{n-1}$. $\endgroup$ – NotDijkstra Jul 3 at 11:10
  • $\begingroup$ @НикитаБабенко Finally, you have the call stack. We could bound the amount of memory necessary for each frame by some constant. But then we have $n$ of such calls, which is the depth of the recursion. $\endgroup$ – NotDijkstra Jul 3 at 11:14
  • $\begingroup$ @НикитаБабенко The analysis doesn't need to end there. Potentially the space for currentSubset and result could be reallocated a few times. You could avoid that by reserving from the beginning the space for them, since you know which sizes they will have. As $n$ increases it is not realistic to reserve a contiguous chunk of space for result in memory. So, the current form of the return value will stop working. $\endgroup$ – NotDijkstra Jul 3 at 11:28
0
$\begingroup$

I dont really know c++, but I can tell you what counts as space complexity:

  1. Everything that creates new data does, and anything that does not create additional data has $O(1)$ space complexity: passing by reference is $O(1)$, passing by value is $O(n)$ (for $n$ being input size).
  2. Looping over an array requires an index, which costs $O(log(n))$ space complexity.
  3. Recursive calls in a function: the program has to remember where it was when calling a function, so when you have a recursive function - each recursion depth adds more to the space complexity.

Also, a really rough estimate to the space complexity is that it's bounded by the time complexity.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for the answer. Why looping over an array takes O(log(n)) space complexity? We only need a single variable, which takes O(1) space, doesn't it? $\endgroup$ – Никита Бабенко Jul 2 at 23:42
  • $\begingroup$ The single variable needs to store a value up to $n$ - the length of the array. Storing that in memory takes log(n) bits, and therefore looping an array takes $O(log(n))$ space complexity $\endgroup$ – nir shahar Jul 2 at 23:43
  • $\begingroup$ Sorry, but i don't agree with you. We store the number in the integer variable, and it's size doesn't affect on the space complexity. It would be still constant. $\endgroup$ – Никита Бабенко Jul 2 at 23:47
  • $\begingroup$ it does affect space complexity: it still takes $\theta(log(n))$ memory no matter what you do, as saving the array size in memory takes log(n) bits. However, usually you don't really count it as $O(log(n))$ memory because it may be the same as $O(1)$ for practical cases. BUT: If your code is recursive, and say has recursion depth $d$, then $d$ copies will be saved and therefore $O(dlog(n))$ space will be used. Beware of that! $\endgroup$ – nir shahar Jul 3 at 0:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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