6

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?

Improve this question
3
  • 1
    Is this your own implementation of a linked list or the one included with Java? Commented Mar 4, 2013 at 0:15
  • @AndrewMarshall: We were given a LinkedList class by the university. It's got all the methods that the LinkedList class had, except size() and get() which we had to write ourselves. Commented Mar 4, 2013 at 0:17
  • FYI, If you're implementing get() and size() calls, you can add a debug variable inside those that count how many times those functions have to call the list's lookup functions (getFirst(), next(), etc). That will give you an answer to the "100" elements portion of the question. Try 1000 and 10000 and it should be fairly obvious what the O notation would be...as well as why you shouldn't loop on Linked Lists this way. Commented Oct 3, 2020 at 21:31

4 Answers 4

Reset to default
9

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

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I agree, and so does @JreJav. However, he specified the O(n) complexity of a single iteration and left it to the reader to "figure out what the time complexity of the whole loop will be." Especially since the question is fairly old, it would be better to have the accepted answer be more clear about the actual answer to the question instead of just a portion of it.
For those who don't quite see it yet...The first get(0) call will look at the first element. The get(1) call will start back at the first element, then traverse to the second...and so on, each traversing elements equal to the index: The call for get(n) will start at index 0 and take n traversals. So as this answer suggests, if the size was 100, then the total traversal count for just the get functions would be 1+2+3+4+5...+100. Calculating the size would take N traversals unless you're keeping track somewhere else. So that's also O(N^2) traversals if it's recalculating each loop iteration.
5

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

Improve this answer

Comments

2

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.

Improve this answer

10 Comments

I've already raised the issue of size being calculated in the loop - certainly not efficient in terms of lookups. Can I ask, why does it take O(2N) which becomes O(n) lookups? Is that the double lookup of size and get?
O(2N) is equivalent to O(N). Constant multipliers and additions factor out. And no, it simply means that you take O(N) for .size() and O(N) for .get(), so the time complexity is O(N + N + C) where C is the other constant-time operations (ones that do not depend on N) in the loop. O(N + N + C) = O(2N + C) = O(2N) = O(N)
I'm assuming if the loop runs n times, it will perform 2n^2 lookups, which becomes n^2 lookups?
Yes. The loop runs for N iterations, so you have O((2N) * N) = O(2N^2) = O(N^2) for the time complexity.
You're a star - and very quick at responding! Thanks
|
2

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.