What does "O(1) access time" mean?

Question

You're going to want to read up on Order of complexity.

http://en.wikipedia.org/wiki/Big_O_notation

In short, O(1) means that it takes a constant time, like 14 nanoseconds, or three minutes no matter the amount of data in the set.

O(n) means it takes an amount of time linear with the size of the set, so a set twice the size will take twice the time. You probably don't want to put a million objects into one of these.

In essence, It means that it takes the same amount of time to look up a value in your collection whether you have a small number of items in your collection or very very many (within the constraints of your hardware)

O(n) would mean that the time it takes to look up an item is proportional to the number of items in the collection.

Typical examples of these are arrays, which can be accessed directly, regardless of their size, and linked lists, which must be traversed in order from the beginning to access a given item.

The other operation usually discussed is insert. A collection can be O(1) for access but O(n) for insert. In fact an array has exactly this behavior, because to insert an item in the middle, You would have to move each item to the right by copying it into the following slot.

O(1) means the time to access something is independent of the number of items in the collection.

O(N) would mean the time to access an item is a proportional to the number (N) of items in the collection.

Every answer currently responding to this question tells you that the O(1) means constant time (whatever it happens to measuring; could be runtime, number of operations, etc.). This is not accurate.

To say that runtime is O(1) means that there is a constant c such that the runtime is bounded above by c, independent of the input. For example, returning the first element of an array of n integers is O(1):

int firstElement(int *a, int n) {
    return a[0];
}

But this function is O(1) too:

int identity(int i) {
    if(i == 0) {
        sleep(60 * 60 * 24 * 365);
    }
    return i;
}

The runtime here is bounded above by 1 year, but most of the time the runtime is on the order of nanoseconds.

To say that runtime is O(n) means that there is a constant c such that the runtime is bounded above by c * n, where n measures the size of the input. For example, finding the number of occurrences of a particular integer in an unsorted array of n integers by the following algorithm is O(n):

int count(int *a, int n, int item) {
    int c = 0;
    for(int i = 0; i < n; i++) {
        if(a[i] == item) c++;
    }
    return c;
}

This is because we have to iterate through the array inspecting each element one at a time.

O(1) does not necessarily mean "quickly". It means that the time it takes is constant, and not based on the size of the input to the function. Constant could be fast or slow. O(n) means that the time the function takes will change in direct proportion to the size of the input to the function, denoted by n. Again, it could be fast or slow, but it will get slower as the size of n increases.

Here is a simple analogy; Imagine you are downloading movies online, with O(1), if it takes 5 minutes to download one movie, it will still take the same time to download 20 movies. So it doesn't matter how many movies you are downloading, they will take the same time(5 minutes) whether it's one or 20 movies. A normal example of this analogy is when you go to a movie library, whether you are taking one movie or 5, you will simply just pick them at once. Hence spending the same time.

However, with O(n), if it takes 5 minutes to download one movie, it will take about 50 minutes to download 10 movies. So time is not constant or is somehow proportional to the number of movies you are downloading.