5
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So any "input" or "global variables" are not considered as work memory? If a local variable is initialised with a size of variable that is not constant, then we can say that it is the work memory? $\endgroup$ – Sarp Kaya Oct 27 '13 at 9:48
  • $\begingroup$ That's right. Only local variables constitute work memory. As for global variables initialized by the algorithm, they are outside of this framework. $\endgroup$ – Yuval Filmus Oct 27 '13 at 16:44
  • $\begingroup$ I am a bit confused about initialising global variables. If I have a 2d pointer array all elements are NULL and initialising values to all of these elements, I still should not consider this as a work memory? $\endgroup$ – Sarp Kaya Oct 28 '13 at 3:26
  • $\begingroup$ Global variables are somewhat outside of this framework. If it's a global variable initialized by some method by used by others, then it should count as global memory. If it's a static (persistent) variable, it should count as work memory, since it's only used by the particular method. The idea is that you want to assign each variable to some body of code in a reasonable way, and you could make up a definition of work memory that would make sense and also satisfy some reasonable properties. But in the end, work memory is here to help you, not confound you. $\endgroup$ – Yuval Filmus Oct 28 '13 at 4:59
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So it is basically the amount of memory that an algorithm accesses, which is both reads and writes? $\endgroup$ – Sarp Kaya Oct 27 '13 at 5:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.