CODEWITHSUNDEEP
algorithmlinked-listspace-complexity
Patel Parth
Patel Parth

Reputation: 315

Confused with space complexity of following algorithm

I was looking at question Link and it tells that space complexity of solution is O(1) (read answer by Max). I have doubt that space complexity is the space which is needed by the algorithm and I had understood that correctly and feels that it is definitely O(n) where n is size of linked list. Can anyone tell that is that answer wrong or I have made mistake in understanding?

Upvotes: 1

Views: 58

Answers (1)

Elliott
Elliott

Reputation: 2623

The summary of the answer in Max's link, here, is clearly mistaken. O(1) space complexity is impossible by definition, if the goal is to copy some variable amount of data (in this case linked list).

This is seen in the algorithm's description:

Create the copy of node 1 and insert it between node 1 & node 2 in original Linked List, create the copy of 2 and insert it between 2 & 3.. Continue in this fashion, add the copy of N afte the Nth node Blockquote

Here, the answerer has just added "N" nodes, so it's at least O(n) complexity (and, indeed, the space complexity of the algorithm listed is O(n)).

Upvotes: 1

Related Questions