Too large in memory

Computer Science Level 4

You want to sort a list of a number of integers. Let's call the number of integers that will arrive to be $n$ , even though you don't know what its value. A special property of this list is that all of them are different, and they all are in the range $[0, n]$ . The list will be delivered online (that is, you only have access to the next item in the list). You also know that the list is huge, so holding the entire list in your memory would be a big problem; you want to keep the memory used as low as possible. How much additional memory do you need?

Details and Assumptions :

Your program has access to an input and an output (input is read-only and output is write-only). Your program can request the next number in the list from the input, and your program can print a number to the output; both of them don't require any additional memory except what you use to store the number read/written. You don't know the number of integers that will arrive; when you read -1 , it means the input has stopped. You must print the integers to the output in the order you wish (that is, sorting them, from smallest to largest). Memory used is measured in the most number of bits used at once during the runtime of your program.

\Theta(1)

\Theta(n^2)

\Theta(n)

\Theta(n \log n)

\Theta(\log n)

None of the others

1 solution

Ivan Koswara
Jan 11, 2016

The answer is $\Theta(\log n)$ . The following program uses only that much additional memory:

Initialize sum := 0, expected_sum := 0, count := 0
Loop forever
    Read a number k from input
    If it's -1, break out from the loop
    Add k to sum
    Add count to expected_sum
    Add 1 to count
Add count to expected_sum
Add 1 to count
Initialize missing_number := expected_sum - sum
For each i from 0 to count (inclusive)
    If i is not missing_number, write i to output

There are $n+1$ possible integers, and $n$ of them appear in the input. Instead of storing everything, we can instead try to look for the missing number. This can be done by adding the entire input, and comparing it to $0 + 1 + 2 + \ldots + n$ ; the deficit gives the missing number. We can now print $0, 1, 2, \ldots, n$ in order, skipping the missing number.

The memory used is only for sum , expected_sum , count , k , and i . We know that count , k , i are bounded above by $n$ , so they use $\log n$ bits each. Additionally, sum and expected_sum are bounded above by $0 + 1 + \ldots + n = \frac{n(n+1)}{2} = \Theta(n^2)$ , so they use $2 \log n$ bits each. In total, that's $7 \log n = \Theta(\log n)$ bits of extra memory.

We also need at least $\Theta(\log n)$ bits for obvious reasons: whatever number we read, we might need to store it (because the only other option is to immediately pump it out to output, which wouldn't sort the list). Thus this is indeed the optimal solution.

Moderator note:

This solution works due to the unique properties of the list, which heavily restricts the possibilities. In such cases, sorting blindly is often not the best approach. Instead, we should try and exploit the various characteristics that are available.

Too large in memory

1 solution

Moderator note:

0 pending reports