CODEWITHSUNDEEP
javadata-structurestime-complexitybig-o
aaronbrodsan
aaronbrodsan

Reputation: 41

Time complexity of LinkedList.subList(int, int)

If I have a linked list of objects and I want the sublist from index 2 to 5. Is this operation o(1)? All you would need to do is null the reference to prev on the node at index 2, and return the node at index 2, correct? Does this require copying the contents of the linked list into another one and returning that or just setting the head to be the node at index 2?

Upvotes: 3

Views: 1777

Answers (3)

user2736738
user2736738

Reputation: 30926

It's O(n) if you consider the general case of the algorithm. Even if you do what you said finding the n-th and m-th element would take a complete traversal of the list.

It's wrong to consider that the finding the sublist from 2 to 5 would be O(1). It is O(1) ofcourse but it needs constant amount of operations to do that but are you creating an algorithm for sublist(2,5)? If you do that then ofcoursse it is always O(1).

A better example is sorting 100 numbers is of O(1) complexity so is sorting 10,000 numbers. But it is not what we are concerned about. We want to know the nature of the algorithm based on the inputs fed to that algorithm.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726589

Is this operation o(1)?

In general, getting a sublist of a linked list is O(k), not O(1)*.

However, for any specific index value, such as 2, 5, or 5000, any operation is O(1), because a specific index becomes a constant that gets factored out from Big-O notation.

* Construction of sublist may be optimized such that you pay construction costs on the first navigation of sublist, rather on construction. In other words, constructing a sublist without iterating it is O(1).

Upvotes: 2

nasukkin
nasukkin

Reputation: 2540

It appears that the sublist method runs in O(1) time. See the source code for the method.

All that this code does is return a new instance of SubList that is initialized with the list that sublist is invoked upon. No iteration is happening here, so the operation runs in constant time.

Upvotes: 0

Related Questions