CODEWITHSUNDEEP
space-complexity
user12408331
user12408331

Reputation:

Why is my textbook saying the space complexity is O(1)?

Why does my textbook say that the space complexity for this algorithm is O(1)? I feel like it is O(n) for the size of the Linked List that it is holding.

 public static LinkedListNode nthToLast(LinkedListNode head, int k) {
    LinkedListNode p1 = head;
    LinkedListNode p2 = head;

    /* Move p1 k nodes into the list.*/
    for (int i = 0; i < k; i++) {
        if (p1 == null) return null; // Out of bounds
        p1 = p1.next;
    }

    /* Move them at the same pace. When p1 hits the end, 
     * p2 will be at the right element. */
    while (p1 != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p2;
}

Upvotes: 1

Views: 828

Answers (3)

MrHappyAsthma
MrHappyAsthma

Reputation: 6522

The space complexity is how much memory the algorithm uses as a function of the size of the input. In other words: if the size of the input changed, how much more memory would the algorithm use?

Whether or not the linked list input has 1 node, 10 nodes, or 1000000 nodes, the algorithm uses the same amount of memory. It uses a constant amount because it only allocates 3 variables (a constant number) -- int i, LinkedListNode p1, and LinkedListNode p2.

UPDATE: It's important to note that p1 and p2 just reference a single node. They are initialized to the reference the value of head, which would just be the first node in the list. Those two variables don't contain the whole list itself.

   head
    |
    v
 [node1] --> [node 2] --> [node 3] --> ..... --> [node n]
  ^   ^
  |   |
 p1   p2

Notice in the drawing above, that if we had 1 node or 20 nodes, you'd still only have a single p1 and p2. They may reference different nodes at different times in the algorithm, but only ever contain a single node each.

Upvotes: 2

anusha
anusha

Reputation: 181

When you think of space complexity of an algorithm, you should consider the additional space that the algorithm explicitly allocates. In the example above, the algorithm to find the nth to last LinkedListNode in the list simply creates two additional LinkedListNode pointers p1 and p2 as well as one counter i for for loop iteration. The amount of additional memory the algorithm allocates has nothing to do with the length of the linked list passed in. You would still use two LinkedListNode pointers and one integer counter regardless of whether the linked list passed to nthToLast() was 10 nodes long or 10 million nodes long. Therefore, this algorithm's space complexity is O(1).

Upvotes: 3

Suma
Suma

Reputation: 34403

The algorithm does O(n) iterations, but it does does not allocate any memory for the elements in the list, it only uses the already existing items. The only memory used is for local variables p1 and p2, used to designate the items.

Upvotes: 0

Related Questions