Retrieval of an arbitrary item from a linked list is O(n). Arbitrary means any of the elements are eligible for selection, without loss of generality.
However, retrieval of a specific item from a linked list has nothing to do with how many items are in the list. It is therefore O(1). Retrieving the 50th item from a linked list takes the same amount of time, no matter whether the list has 50 elements, 50M elements, or 50^50! elements.
I'm not sure what you mean by caching. We are just talking about the standard linked list implementation with a head pointer, and where each node has a next pointer, and nothing more.
I make the following claims:
The original claim was
Retrieving the 10^(10!)th item in a linked list is "O(1)"
To my eye it's trivial to see where you go wrong i.e.
Retrieving the nth item in a linked list is "O(n)"
But i expect you to try and escape on a technicality.
Further claimed was
However, retrieval of a specific item from a linked list has nothing to do with how many items are in the list. It is therefore O(1)
This is (one place) where you go wrong. The number of items in a data structure is not the only consideration in big o analysis of an algorithm.
In the case of retrieving an item from a linked list, another factor that must be considered is the index of the item you are retrieving. And quickly you find that the higher the index, the higher the cost of retrieval. Classic O(n). Easy to see when you set k == n. That's worst case big o analysis of linked list retrieval. Average case is also O(n) because on average it'll take n / 2 operations to retrieve an element from the list, and the 1 / 2 is a constant factor we disregard, since the total cost still scales linearly in proportion with n.
Things that are O(1) take the same amount of time regardless of the input. Critically, you must allow input to vary to make a O(1) claim. Retrieving at item from an array is a classic example of this. No matter what the index of the item you wish to retrieve is, you perform the same number of steps to get it. Multiply the size of the type by the index and add to the address of the first element. Works the same for any index.
If you can change the input and get a different runtime, you're not dealing with a O(1) algo. I think this is clearly true for retrieving an item from a linked list.
You can't use big o analysis the way you're trying to do it. You don't get to cherry pick the input and say "Because I always choose 10, and because that always takes the same amount of time, the operation is O(1)."
You can say "This input always takes the same amount of time" but that doesn't tell you anything about the characteristics of the underlying algorithm. You certainly can not claim to make a statement about big o runtime based only on one datapoint.
Fundamentally you are using big o analysis wrong.
In order to make a big o claim you have to allow the input to vary.
Otherwise you're just saying "Doing x takes y long" but you certainly cannot use big o notation to describe that. Not correctly at least.
Things that are O(n) scale in direct proportion to n. To retrieve the nth item from a linked list you have to visit all n elements. There are no shortcuts, and the critical part to understand is that the input you choose dictates the runtime of the algorithm.
I think the other main place you go crooked is by thinking that knowing n (or k as you call it) changes anything.
Being able to predict the cost of an operation does not make it O(1).
Getting the same cost when performing the same operation on the same type of data structure does not make the algorithm O(1). You don't get to just consider size of the data structure and disregard all other factors when doing big o analysis.
You're not wrong to say
Retrieving the 50th item from a linked list takes the same amount of time, no matter whether the list has 50 elements, 50M elements, or 50^50! elements.
But that doesn't mean
retrieval of a specific item from a linked list [...] is therefore O(1)
It's still O(n), where n is the index you want to retrieve. The cost of the operation can be described in general terms in proportion to the input. The cost of retrieving an item from a linked list varies according to the index of the item. Even if you know the index, even if you can calculate the cost before running the algorithm, that doesn't change the big o analysis of the algorithm to O(1). It's still O(n), you just happen to know the cost of this O(n) specificially instead of talking about the characteristics of the algo generally.
Things that are O(1) take the same amount of time regardless of the input. Critically, you must allow input to vary to make a O(1) claim.
I do allow the input to vary. Give me any linked list you like, and I can write you an O(1) time method that always takes the same asymptotic time to retrieve the 50th item -- a specific index.
If you say "well, you have to let me pick any item I want, not just the thing at index 50", then you are picking an arbitrary item, not a specific item. I do agree that retrieving an arbitrary item from a linked list is O(n) in time with respect to the size of the items in the list.
I think you might be conflating the definitions of "arbitrary" and "specific", and that is why you don't agree with me:
arbitrary (adjective):
- of unspecified value
specific (adjective):
- clearly defined or identified
But those are very different things. That's why the O(1) result is a little surprising, and it's why I think I'm correct in stating that, for a linked list, retrieving arbitrary items is O(n) and retrieving the item at a specific index is O(1).
Before you say "well that's trivial and degenerate", not every data structure has this "O(1) for a specific index" property. Extracting the third rope from a ten-rope knot takes more time when there are ten ropes instead of three.
We can prove this claim, by proving two lemmas:
The first claim is straightforward, and we can use our intuitive understanding of O-notation. It takes k-steps to jump through k elements in a linked list, so not having any more information (like how the linked list is stored or elements cached), we can conclude that the worst-case runtime will be no better than O(k). You can also verify this with the formal definition (below), but that's left as an exercise for the reader ;)
Now, for the second claim, let's go to the definition. The wikipedia page ( http://en.wikipedia.org/wiki/Big_O_notation ) is fairly dense, so I much prefer the definition in "Introduction to Algorithms" by Cormen, Leiserson, and Rivest (my version is from 1998, so no Stein):
For a given function g(n), we denote by O(g(n)) the set of functions
O(g(n)) = { f(n) : there exist positive constants c and n0 such that 0 ≤ f(n) ≤ c g(n) for all n ≥ n0 }
In our problem, g(n) = 1 and f(n) = k
So to prove that O(k) is a proper subset of O(1), we need only find the positive constants c and n0 that satisfy this formula. Well, we can use whatever we want for n0, since n doesn't appear in either of our equations. Let's use 1 to simplify things. Now for choosing c, we can use any number greater than or equal to k, so how about k? Now we have:
∀n > 1, 0 ≤ k ≤ k * 1
⇒ f(n) ∈ O(g(n))
∴ O(k) = O(1)
Stunned you won't give up on this.
You guys are so wrong I'm seriously shaking my head over here. This is the last I'm going to say on the subject and if you have any more to say other than "I owe you a beer" then it better "I'm very sorry, you were right."
finding the kth element in a linked list is O(k) for any constant k
No. Just no. Finding the kth element in a linked list is O(n). Always. Specific or arbitrary. It so happens that the number of operations needed to reach a particular index is approximately equal to that index, but that doesn't mean that it runs in constant time. In fact that's exactly why it runs in O(n), or linear time. The runtime scales linearly with the index selected.
The fact that the runtime is identical on lists of different lengths is irrelevant and a red herring. What is relevant is that to reach the nth item you have to traverse all n - 1 elements before n.
It also happens that the number of operations to find the nth element is not affected by the length of the list, but again that doesn't mean it runs in constant time. The critical issue is that the runtime is affected by the selection of n.
Even if you don't vary n, the runtime is still affected by, and linearly proportional to, n. That's what makes it a O(n) algo.
Put another way, just because the run time is the same on different linked lists, doesn't mean that the algo runs in constant time. It's still running in linear time, you're just keeping the index you're looking up constant. A subtle, but important distinction.
If finding the kth element always took m operations, regardless of the value of k, then finding the kth element in a linked list would be O(m) which would then reduce to O(1). Unfortunately, because the index and cost of retrieval increase together in lock-step, no such claim can be made.
Big o is for talking about comparative or relative complexity, it is not a method for obtaining a specific count of steps. When you bring big o into it you are making a generalization and the only generalization that fits is that the runtime is linearly proportional to the index in question.
Specifically, if you're making a claim about the big o complexity for finding the nth item in a list, even if you don't intend to vary n (like by always choosing 50), any claim you make has to generalize to other values of n. Otherwise you're not doing big o. I don't know what you are doing but it isn't big o. And you sure as hell can't start saying O(this) or O(that).
BTW saying "finding the kth element takes k operations" is exactly the same as saying 'it runs in linear time" which is exactly the definition of O(n) algos.
Give me any linked list you like, and I can write you an O(1) time method that always takes the same asymptotic time to retrieve the 50th item -- a specific index.
No, barring some weird definition of 'linked list' the best you can do is write me a O(n) algo that always returns in the same amount of time because you're not varying n. If you did vary n runtime would change. In a true O(1) algo, such as indexing into an array, the runtime is the same no matter what index is selected. In your examples runtime is dependent on the index selected. That's a huge red flag that what we're dealing with is not a constant time algo.
Refusing to vary n is not sufficient to turn a O(n) algo into a O(1) algo.
If the index did vary you'd quickly appreciate the difference between a linear and a constant time algo.
Again, the original claim was
Retrieving the 10^(10!)th item in a linked list is "O(1)"
In a final desperate plea, I'm going to appeal to authority and link to the wikipedia page on this, which for the record I've only consulted for the first time just now. Note the use of the word specific @jf you smart-ass.
http://en.wikipedia.org/wiki/Linked_list#Speeding_up_search
I expect beers from both of you next we meet. :D
So..In the language of your choice, how do you retrieve your specific item in the first place in a way which doesn't go through the O(n) search overhead? If you've already done the search and are just using the cached results, sure, that's O(1) ("cache" lookup), but if you haven't previously searched-and-found the item (or sorted the list?)...