Example: Integers

How much memory does an integer use? This might sound like a stupid question – don’t we usually just assume that integers use a fixed size, such as 32 bits or 64 bits?

Yes and no – most programming languages have fixed-size integers, and then their space usage is constant, $O(1)$. But fixed-size integers are actually just an approximation of integers. A 64-bit integer can only store values in the range $-2^{63}$ to $2^{63}$, and although this is enough for most purposes there are cases when we need to calculate integers of arbitrary size. Most modern languages have a special datatype for arbitrary-size integers (e.g., Javascript has BigInt and Java has BigInteger), while languages such as Python even has arbitrary-size integers as the default numeric type.

So, how much memory does in arbitrary-size integer use? Normally they need a number of bytes that is proportional to the number of bits in the binary representation. The space usage is therefore $O(n)$, where $n$ is the length of the binary representation.

But what is the space usage in terms of the integer itself? This boils down to the question how many bits are there in the binary representation of a number. Since you can store $2^n$ different integers in $n$ bits, we need a logarithmic number of bits to store an arbitrary integer. Therefore the space usage of an integer is logarithmic, $O(\log n)$ to store an integer $n$.

Example: Friendship links

Imagine that we want to keep track of friendships between $n$ people. We can do this with a 2-dimensional array of size $n \times n$ (a matrix). Each row of the matrix represents the friends of an individual, with the columns indicating who has that individual as a friend. For example, if person $j$ is a friend of person $i$, then we place a mark in column $j$ of row $i$ in the array. Likewise, we should also place a mark in column $i$ of row $j$ if we assume that friendship works both ways. For $n$ people, the total size of the matrix is in $O(n^2)$.

But is this the best representation of friendship links? Assume that $n$ grows large, and we want to include every person in Sweden (which has around $10M$ people). Then the matrix will have around $(10^7)^2 = 10^{14}$ cells. How many friends will an average person have? This varies of course, but it’s extremely unlikely that they have more than say 100 friends. So the total number of friendship links should be at most around $10M\times 100 = 10^9$, which is several orders of magnitudes less than the size of the matrix. So is there a better representation?

Instead of storing a $n\times n$ matrix, we can store an array of size $n$ with pointers to lists of numbers. Now, if array cell $j$ points to a list containing $i$, then person $j$ is a friend of person $i$. How many friends does a person have, on average? Of course we cannot know that, but it sounds reasonable that the average number of friends does not depend on the size of the dataset. That it doesn’t depend on the size $n$ is just another way of saying that it is bounded by some constant $k$. Now, our array of friendship lists will consist of one array of size $n$ and $n$ lists of size $k$ (on average). So, the average space usage will be $O(n) + n\cdot O(k) = O(n) + O(n) = O(n)$. With this new representation we could reduce the space complexity from quadratic $O(n^2)$ to linear $O(n)$.

Example: Quicksort

How much additional space does Quicksort use? Just as Mergesort, Quicksort is also a divide-and-conquer algorithm, but in this case we cannot be certain that it halves the problem size in each call. We have already showed that Quicksort is quadratic $O(n^2)$ in the worst case (if we are unlucky with the pivot selection).

Now, Quicksort is a recursive algorithm, and whenever we make a recursive call the system has to allocate some memory for storing information on what to do when returning from the recursion. This is done by pushing some memory block (of constant size) onto the call stack. But when Quicksort is unlucky and gets quadratic behaviour, it will use a linear number of recursion levels. Therefore the additional memory usage for Quicksort is linear $O(n)$, so it is not in-place.

But let’s assume that we have a good pivot selection algorithm (and well-behaved input), so that we get the normal $O(n \log n)$ behaviour. Quicksort will still allocate memory on the call stack for the recursive calls, and just as Mergesort we will never get fewer than $O(\log n)$ recursive levels. Therefore the additional memory usage for Quicksort will be at least logarithmic $O(\log n)$ in the worst case.

Example: Binsort

Another example of the space/time tradeoff is typical of what a programmer might encounter when trying to optimise space. Here is a simple code fragment for sorting an array of integers. We assume that this is a special case where there are $n$ integers whose values are a permutation of the integers from 0 to $n-1$. This is an example of a binsort. Binsort assigns each value to an array position corresponding to its value.

newArr = new Array(arr.size)
for i in 0 .. arr.size-1:
    newArr[arr[i]] = arr[i]

This is efficient and requires $O(n)$ time. However, it also requires two arrays of size $n$, so the additional space usage is $O(n)$.

Next is a code fragment that places the permutation in order but does so within the same array (thus it is an example of an in-place sort).

for i in 0 .. arr.size-1:
    while arr[i] != i:
        swap(arr, i, arr[i])  // Swap element arr[i] with arr[arr[i]]

The function swap(arr,i,j) exchanges elements i and j in array arr. It may not be obvious that the second code fragment actually sorts the array. To see that this does work, notice that each pass through the for loop will at least move the integer with value $i$ to its correct position in the array, and that during this iteration, the value of arr[i] must be greater than or equal to $i$. A total of at most $n$ swap operations take place, because an integer cannot be moved out of its correct position once it has been placed there, and each swap operation places at least one integer in its correct position. Thus, this code fragment has cost $O(n)$, just as the first fragment. However, it requires more time to run than the first code fragment. On an ordinary computer the second version takes nearly twice as long to run as the first, but it only needs constant additional space (for the i variable).