[big-o] What does "O(1) access time" mean?

I have seen this term "O(1) access time" used to mean "quickly" but I don't understand what it means. The other term that I see with it in the same context is "O(n) access time". Could someone please explain in a simple way what these terms mean?

See Also

• What is Big O notation? Do you use it?
• Big-O for Eight Year Olds?

It's called the Big O notation, and describes the search time for various algorithms.

O(1) means that the worst case run time is constant. For most situation it means that you dont acctually need to search the collection, you cand find what you are searching for right away.

It means that the access takes constant time i.e. does not depend on the size of the dataset. O(n) means that the access will depend on the size of the dataset linearly.

The O is also known as big-O.

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.

Basically, O(1) means its computation time is constant, while O(n) means it will depend lineally on the size of input - i.e. looping through an array has O(n) - just looping -, because it depends on the number of items, while calculating the maximum between to ordinary numbers has O(1).

Wikipedia might help as well: http://en.wikipedia.org/wiki/Computational_complexity_theory

It means that access time is constant. Whether you're accessing from 100 or 100,000 records, the retrieval time will be the same.

In contrast, O(n) access time would indicate that the retrieval time is directly proportional to the number of records you're accessing from.

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.

"Big O notation" is a way to express the speed of algorithms. n is the amount of data the algorithm is working with. O(1) means that, no matter how much data, it will execute in constant time. O(n) means that it is proportional to the amount of data.

The easiest way to differentiate O(1) and O(n) is comparing array and list.

For array, if you have the right index value, you can access the data instantly. (If you don't know the index and have to loop through the array, then it won't be O(1) anymore)

For list, you always need to loop through it whether you know the index or not.

According to my perspective,

O(1) means time to execute one operation or instruction at a time is one, in time complexity analysis of algorithm for best case.

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.

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.

O(1) means Random Access. In any Random Access Memory, the time taken to access any element at any location is the same. Here time can be any integer, but the only thing to remember is time taken to retrieve the element at (n-1)th or nth location will be same(ie constant).

Whereas O(n) is dependent on the size of n.

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) always execute in the same time regardless of dataset n. An example of O(1) would be an ArrayList accessing its element with index.

O(n) also known as Linear Order, the performance will grow linearly and in direct proportion to the size of the input data. An example of O(n) would be an ArrayList insertion and deletion at random position. As each subsequent insertion/deletion at random position will cause the elements in the ArrayList to shift left right of its internal array in order to maintain its linear structure, not to mention about the creation of a new arrays and the copying of elements from the old to new array which takes up expensive processing time hence, detriment the performance.

Introduction to Algorithms: Second Edition by Cormen, Leiserson, Rivest & Stein says on page 44 that

Since any constant is a degree-0 polynomial, we can express any constant function as Theta(n^0), or Theta(1). This latter notation is a minor abuse, however, because it is not clear what variable is tending to infinity. We shall often use the notation Theta(1) to mean either a constant or a constant function with respect to some variable. ... We denote by O(g(n))... the set of functions f(n) such that there exist positive constants c and n0 such that 0 <= f(n) <= c*g(n) for all n >= n0. ... Note that f(n) = Theta(g(n)) implies f(n) = O(g(n)), since Theta notation is stronger than O notation.

If an algorithm runs in O(1) time, it means that asymptotically doesn't depend upon any variable, meaning that there exists at least one positive constant that when multiplied by one is greater than the asymptotic complexity (~runtime) of the function for values of n above a certain amount. Technically, it's O(n^0) time.