CODEWITHSUNDEEP
c++arraysspace-complexity
David
David

Reputation: 123

Space complexity of an array of pairs

So I'm wondering what the space complexity of an array of integer pairs is?

std::pair<int,int> arr[n];

I'm thinking that, because a pair is constant and the array is n, the space complexity is O(2) * O(n) = O(2n) = O(n). Or is the space complexity O(n^2) because the array of pairs is still essentially a 2D array?

Upvotes: 3

Views: 1951

Answers (3)

javidcf
javidcf

Reputation: 59731

The space complexity of an array can in general be said to be:

O(<size of array> * <size of each array element>)

Here you have:

std::pair<int,int> arr[n];

So arr is an array with n elements, and each element is a std::pair<int,int>. Let's suppose an int takes 4 bytes, so a pair of two int should take 8 bytes (this numbers could be slightly different depending on the implementation, but that doesn't matter for the purposes of complexity calculation). So the complexity would be O(n * 8), which is the same as O(n), because constants do not make a difference in complexity.

When would you have something like O(n^2)? Well, you would need a multi-dimensional array. For example, something like this:

std::pair<int,int> arr[n][m];

Now arr is an array with m elements, but each element is in turn an array of n std::pair<int,int> elements. So you have O(m * <size of array of n pairs>), which is to say O(m * n * 8), that is, O(m * n). If m happens to be the same as n, then you get O(n * n), or O(n^2).

As you can imagine, the same reasoning follows for any number of array dimensions.

Upvotes: 3

Xirema
Xirema

Reputation: 20396

The correct Space complexity is O(n)

The fact that it superficially resembles a 2D array is immaterial: the magnitude of the second dimension is known, and as such, it remains O(n). This would also be true if the pairs were, instead, 100-element arrays. Because the dimensions of the elements (each a 100 element array) is known, the Space complexity of the structure is O(100 * n) which is O(n).

Conversely, however, if the elements were instead explicitly always the same as the size of the container as a whole, i.e. this were something like this:

int n = /*...*/;
std::vector<std::vector<int>> arr(n);
for(std::vector<int> & subarr : arr) {
    subarr.resize(n);
}

Then it would indeed be O(n2) instead. Because now both dimensions are depending on an unknown quantity.

Conversely, if the second dimension were unknown but known to not be correlated to the first dimension, you'd instead express it as O(nm), i.e. an array constructed like this:

int n = /*...*/;
int m = /*...*/;
std::vector<std::vector<int>> arr(n);
for(std::vector<int> & subarr : arr) {
    subarr.resize(m);
}

Now this might seem contradictory: "But Xirema, you just said that if we knew the dimensions were n X 100 elements, it would be O(n), but if we substitute 100 for m, would we not instead have a O(nm) or O(100n) space complexity?"

But like I said: we remove known quantities. O(2n) is equivalent to O(5n) because all we care about is the unknowns. Once an unknown becomes known, we no longer include it when evaluating Space Complexity.

Space complexity (and Runtime Complexity, etc.) are intended to function as abstract representations of an algorithm or data structure. We use these concepts to work out, at a high level conception, how well they scale to larger and larger inputs. Two different data structures, one requiring 100 bytes per element, another requiring 4 bytes per element squared, will not have consistent space ranks between each other when scaling from a small environment to a large environment; in a smaller environment, the latter data structure will consume less memory, and in a larger environment, the former data structure will consume less memory. Space/Runtime Order complexity is just a shorthand for expressing that relationship, without needing to get bogged down in the details or semantics. If details or semantics are what you care about, then you're not going to just use the Order of the structure/algorithm, you're going to actually test and measure those different approaches.

Upvotes: 5

Artyer
Artyer

Reputation: 40891

The space taken is n * sizeof(std::pair<int, int>) bytes. sizeof(std::pair<int, int>) is a constant, and O(n * (constant)) == O(n).

Upvotes: 4

Related Questions