Skip to content

Instantly share code, notes, and snippets.

@fj
Created December 15, 2012 20:46
Show Gist options
  • Save fj/4299037 to your computer and use it in GitHub Desktop.
Save fj/4299037 to your computer and use it in GitHub Desktop.

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.

@deathbob
Copy link

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment