Memory complexity?

Question

I am unclear about finding the memory complexity of an algorithm.

Some places refer memory complexity as what container would be carrying for instance:

for i = 1 to n-1
     if d[i] == d[i + 1]
           d[i] = (d[i] + 5) mod 13

Is considered as having $\theta(N)$ memory complexity.

At some other places how much data we write to a container is a complexity for instance:

reverse_list(n)

    Stack res
    while (n != NULL)
         res push n
         n = n->next
    while (res != null) 
         a = pop res
         print a

Is considered as having a memory complexity of $\theta(N)$ too. Moreover:

Such thing is considered having $\theta(1)$ memory complexity

reverse_list(head)
    last = NULL;
    while(last != head)
        current = head
        while(current->next != last)
            current = current->next
        print current
        last = current

I know how these algorithms work and what they do, but I don't understand how are we meant to be analysing their memory complexity. Could someone explain that please?

Answer 1

Memory complexity is the size of work memory used by an algorithm. In the relevant Turing machine model, there is an read-only input tape, a write-only output tape, and a read-write work tape; you're interested only in the work tape. This makes sense since work memory is the additional memory that the specific algorithm uses. For example, if it is called recursively, then it is only this additional memory that is added per each recursive call.

Under this definition, the first code snippet that you provided uses $O(1)$ memory (when memory is measured in machine words rather than bits). Perhaps the algorithm enclosing it allocates the array d, and in that case the memory taken by the array is considered work memory; but if the array is given as an input, then it isn't considered work memory.

The second algorithm constructs a list of size $N$ (where $N$ is the length of the input), and so uses $\Theta(N)$ work memory. The third algorithm uses two local variables, and so uses $\Theta(1)$ work memory.

Answer 2

The memory complexity of an algorithm is the amount of memory it uses.

(Just like the fact that the time complexity of an algorithm is the amount of computing time it uses.)

If the inputs to the algorithm take more than $\Theta(1)$ space, sometimes we might use the phrase "memory complexity" to refer to the amount of extra memory the algorithm requires, over and above whatever is needed to store the inputs.