Space efficiency of algorithms...

Question

It seems like none of the algorithm textbooks mentions about space efficiency as much, so I don't really understand when I encounter questions asking for an algorithm that requires only constant memory.

What would be an example of a few examples of algorithms that uses constant memory and algorithms that doesn't use constant memory?

Answer 1

Very easy example: counting a number of characters in a string. It can be iterative:

int length( const char* str )
{
    int count = 0;
    while( *str != 0 ) {
       str++;
       count++
    }
    return count;
}

or recursive:

int length( const char* str )
{
    if( *str == 0 ) {
        return 0;
    }
    return 1 + length( str + 1 );
}

The first variant only uses a couple of local variables regardless of the string length - it's space complexity is O(1). The second if executed without recursion elimination requires a separate stack frame for storing the return address and local variables corresponding to each depth level - its space complexity is O(n) where n is string length.

Answer 2

If an algorithm:

a) recurses a number of levels deep which depends on N, or

b) allocates an amount of memory which depends on N

then it is not constant memory. Otherwise it probably is: formally it is constant-memory if there is a constant upper bound on the amount of memory which the algorithm uses, no matter what the size/value of the input. The memory occupied by the input is not included, so sometimes to be clear you talk about constant "extra" memory.

So, here's a constant-memory algorithm to find the maximum of an array of integers in C:

int max(int *start, int *end) {
    int result = INT_MIN;
    while (start != end) {
        if (*start > result) result = *start;
        ++start;
    }
    return result;
}

Here's a non-constant memory algorithm, because it uses stack space proportional to the number of elements in the input array. However, it could become constant-memory if the compiler is somehow capable of optimising it to a non-recursive equivalent (which C compilers don't usually bother with except sometimes with a tail-call optimisation, which wouldn't do the job here):

int max(int *start, int *end) {
    if (start == end) return INT_MIN;
    int tail = max(start+1, end);
    return (*start > tail) ? *start : tail;
}

Here is a constant-space sort algorithm (in C++ this time), which is O(N!) time or thereabouts (maybe O(N*N!)):

void sort(int *start, int *end) {
    while (std::next_permutation(start,end));
}

Here is an O(N) space sort algorithm, which is O(N^2) time:

void sort(int *start, int *end) {
    std::vector<int> work;
    for (int *current = start; current != end; ++current) {
        work.insert(
            std::upper_bound(work.begin(), work.end(), *current),
            *current
        );
    }
    std::copy(work.begin(), work.end(), start);
}

Answer 3

Take a sorting algorithms on an array for example. You can either use an new array of the same length as the original array where you put the sorted elements into (Θ(n)). Or you sort the array in-place and just use one additional temporary variable for swapping two elements (Θ(1)).