Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I was going through this heavily discussed and highly voted question on SO and stumbled across one comment that got 5 upvotes.

So I assume this was a great comment.But it got my head spinning at the same time. Can any one explain this comment? The comment says:

You can't compare big-O values directly without thinking about constant factors. For small lists (and most lists are small), ArrayList's O(N) is faster than LinkedList's O(1).

share|improve this question

migrated from stackoverflow.com Jul 19 '12 at 16:00

This question came from our site for professional and enthusiast programmers.

    
I don't understand the claim that inserting in middle of a linked list is O(1). It might be possible if it is right in the middle, but I don't think that it can be O(1) with arbitrary position in the middle of a linked list. –  nhahtdh Jul 19 '12 at 15:19
3  
@nhahtdh insert in middle of linked list is O(1) , assuming if you have a reference to the position where the new item has to be inserted. otherwise it is obviously O(N). –  Geek Jul 19 '12 at 15:21
    
@nhahtdh while searching for the spot to insert is O(N) on a linked list, the actual insertion is always O(1) compared to the O(N) moving of elements of an array after searching in probably O(lgN) time. –  Peter Smith Jul 19 '12 at 16:55
    
@PeterSmith: The O(log n) argument is invalid. And shifting the elements is the same for both linked list and array list. For linked list you search for the place then insert. For array list, you will shift elements from the back and insert. –  nhahtdh Jul 19 '12 at 17:09
1  
@PeterSmith this is the fallacy of the notation, although a search + insert would be O(N) for both linked and array lists, there is a HUGE difference in performance between scanning through the list for a number and moving every item in the list. Try insertion sorts on linked and array lists yourself to see, I once fixed some code by replacing "Array" with "Linked" and the system went from taking 5 minutes to display a large pulldown list to a few seconds. –  Bill K Jul 19 '12 at 19:52
show 2 more comments

4 Answers

up vote 12 down vote accepted

all O(1) means is that it takes constant time, but not necessarily 1 unit of time. So for a concrete example, let's say the LinkedList takes 3 seconds to access any element. This is in constant time, but it is fairly slow. It is not hard to imagine a situation where we have an Arraylist with O(n) access, but where n is small enough that no element would take more than 2 seconds to access. In such cases, the ArrayList would actually be faster than the LinkedList.

share|improve this answer
1  
this is basically correct, but the linked list vs array list example is terrible. If a list is small the time to find the nth element will be about equal for either an array list or a linked list. Big O doesn't really matter until N is large. A better example is a binary search tree with O(log n) vs a hash map with O(1). The hash function is constant in time, but could be slower than binary search tree O(log n) for small values of N. Since it's constant, it will at some point (for large n) be less than log n. –  Kevin Jul 19 '12 at 18:33
add comment

The definition of O(f(n)) means that the specified algorithm's running time is less than or equal to c*f(n), for some c > 0, and for some n > n' (i.e. large values of n going towards infinity).

So O(1) implies that the running time is less than some constant, say j.

And O(n) implies that the running time is less than some constant, say k, times n. So k*n.

Since we're assuming the lists are small, that means that n is a very small number. Now, depending on implementation, the values of j and k can vary as well. It is entirely possible for the O(1) constant time to be very long, say on the order of seconds. And it is also possible that the O(n) constant factor could be very short, say on the order of microseconds. In this case, with a small value of n, it is clear that the O(n) algorithm can outperform the O(1) algorithm (n microseconds vs. a few seconds).

The original statement is definitely correct - you really can't compare Big-O easily without considering constants, but mainly at small values of n. Once you get to larger values, the differences become more clear.

share|improve this answer
add comment

The definition of BigO means that you've defined a function where you've bounded the running time as a function of the input size, for all values greater than some constant factor.

What is a constant factor? Basicaly it's the part of the running time that doesn't depend on the input size. Lets say your linked list was stored in China. Even though it's O(1), every operation involves a flight to china. That's a constant factor, it never changes. However, the scalability of the algorithm is still O(1) because the flight to China is the same amount of time independent of the number of items in the list.

So yes, this statement is true in practice: "You can't compare big-O values directly without thinking about constant factors."

this statement is likely not true, it's implementation dependent: " For small lists (and most lists are small), ArrayList's O(N) is faster than LinkedList's O(1)."

share|improve this answer
    
The discussion was about adding new elements where the array has to be shifted around but the linked list can just change two pointers –  Affe Jul 19 '12 at 15:24
add comment

Ever heard of a Fibonacci heap? That's an infamous example of huge constant factor. See here: SO on Fibonacci heap

Every big-O notation hides a constant factor behind it. A O(N) function could be f(N) = N or g(N) = 100000000N; similarly, O(1) could be t(N) = 1 or k(N) = 100000000000.

In the above example, for f(N) and k(N), when N < 100000000000, the linear time f(N) is actually faster than the constant time k(N).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.