CODEWITHSUNDEEP
javalinked-list
Andrew Martin
Andrew Martin

Reputation: 5761

Complexity of calling get() on a LinkedList in a for loop using O notation

I've a uni practical to determine the complexity of a small section of code using the O() notation.

The code is:

for (int i = 0; i < list.size(); i++)
    System.out.println(list.get(i));

The list in question is a linked list. For our practical, we were given a ready made LinkedList class, although we had to write our own size() and get() methods.

What is confusing me about this question is what to count in the final calculation. The question asks:

How many lookups would it make if there 100 elements in the list? Based on this, calculate the complexity of the program using O() notation.

If I am just counting the get() method, it will make an average of n/2 lookups, resulting in a big O notation of O(n). However, each iteration of the for loop requires recalculating the size(), which involves a lookup (to determine how many nodes are in the linked list).

When calculating the complexity of this code, should this be taken into consideration? Or does calculating the size not count as a lookup?

Upvotes: 6

Views: 22325

Answers (4)

Eduardo macedo
Eduardo macedo

Reputation: 822

Short answer: It depends on the interpretation of the question.

If the question is asking how many times I will have to jump the list if I want to find 100th position (like calling .get(100)), the complexity would be O(N) since I need to go through the entire list once.

If the question is asking for the complexity of finding an ith variable by checking each index ( like .get(1), .get(2), ..., .get(100)), the complexity would be O(N²) as explained by michael.

Long answer:

The complexity of calculating the size depends on your implementation. If you traverse the entire list to find the size, the complexity would be O(N) for the size calculation (and O(2N) in the first case, O(N² + N) in the second) <- this last part also depends on your implementation as I'm thinking you're calculating the size out of the for-loop.

if you have the size saved as an instance variable that gets bigger every time an element is added, you'll have O(1) for the size and the same complexity for first and second case.

The reason why we round O(2N) (or any case of O(aN + b)) to O(N) is because we care only about the growth of time spent to process the data. If N is small, the code would run fast anyways. If N is big, the code might run in a lot more time depending of the complexity but the constants a and b wouldn't be of much effect when compared with a worse complexity implementation.

Suppose a code runs in 2 seconds for a small input N in O(N) complexity.
as the value gets bigger: N, 2N, 3N, 4N, ..., kN
if the code has complexity O(N) the time would be: 2, 4, 6, 8, ..., 2k
if the code has complexity O(2N) the time would be: 4, 8, 12, 16, ..., 2k * 2
if the code has complexity O(N²) the time would be: 4, 16, 36, 64, ..., (2k)²

As you can see the last implementation is getting out of hand really fast while the second is only two times slower than a simple linear. So O(2N) is slower but it's almost nothing compared to a O(N²) solution.

Upvotes: 2

user2648943
user2648943

Reputation:

I might be bit late to answer, but I think this for loop would actually be O(n^2)

Explanation

Each loop iteration you would be accessing the ith index of the list. Your call sequence would therefore be:

sequence

This is because each iteration i is incremented, and you are looping n times.

Therefore, the total number of method calls can be evaluated using the following sum:

enter image description here

Upvotes: 9

Sahin Habesoglu
Sahin Habesoglu

Reputation: 109

In Java LinkedList, get(int) operation is O(N), and size() operation is O(1) complexity.

Upvotes: 5

jonvuri
jonvuri

Reputation: 5940

Since it is a linked list, to determine the size will be an O(N) operation, since you must traverse the whole list.

Also, you miscalculated the time complexity for .get(). For big-O, what matters is the worst case computation. For a linked list, the worst case of retrieval is that the element is at the end of the list, so that is also O(N).

All told, your algorithm will take O(2N) = O(N) time per iteration. I hope you can go from there to figure out what the time complexity of the whole loop will be.

By the way, in the real world you would want to compute the size just once, before the loop, precisely because it can be inefficient like this. Obviously, that's not an option if the size of the list can change during the loop, but it doesn't look like that's the case for this non-mutating algorithm.

Upvotes: 2

Related Questions