Пространственная сложность кода подмножеств при использовании битовой маски ⇐ C++

[Anonymous]

Рассмотрим утверждение:

Код: Выделить всё

string bitmask = bitset(i).to_string().substr(32 - n);

n — размер вектора.
Какова должна быть пространственная сложность для этого?
Я считаю, что это должно быть O(logN).
В большинстве мест, которые я вижу, говорят, что сложность пространства для этого должна быть O(N).
По моему мнению, если мы не учтем пространство, используемое в буфере, сложность пространства для этого не превысит O(logN).
Предположим, что вектор имеет размер 10, в конечном итоге переменная битовая маска будет уменьшена до формы 0000 - 1111. Поэтому не должна ли пространственная сложность быть O(logN) вместо O(N). По сути, переменная битовой маски хранит символы logN + 1 в любой момент времени. Значит, должно быть O(logN)
Я прав или что-то упускаю?
Я пытаюсь определить пространство сложность для этого кода:
Не включая сложность выходного пространства.

Код: Выделить всё

class Solution {
public:
vector subsets(vector& nums) {
int n = nums.size();
vector output;
for (int i = pow(2, n); i < pow(2, n + 1); ++i) {
// generate bitmask, from 0..00 to 1..11
string bitmask = bitset(i).to_string().substr(32 - n);
// append subset corresponding to that bitmask
vector curr;
for (int j = 0; j < n; ++j) {
if (bitmask.at(j) == '1') curr.push_back(nums[j]);
}
output.push_back(curr);
}
return output;
}
};

В ответах указано, что это O(N)

Подробнее здесь: https://stackoverflow.com/questions/786 ... ng-bitmask