Skip to main content
edited tags
Link
Sarp Kaya
  • 381
  • 2
  • 4
  • 11
Tweeted twitter.com/#!/StackCompSci/status/394398460298153984
Source Link
Sarp Kaya
  • 381
  • 2
  • 4
  • 11

Memory complexity?

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?