Reputation: 5761
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
Reputation: 822
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.
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
Reputation:
I might be bit late to answer, but I think this for loop would actually be
Explanation
Each loop iteration you would be accessing the ith index of the list. Your call sequence would therefore be:
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:
Upvotes: 9
Reputation: 109
In Java LinkedList, get(int) operation is O(N), and size() operation is O(1) complexity.
Upvotes: 5
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