Constant Time Notation: O(1) Style Algorithms

In computer science, Big O notation is used to describe the performance or complexity of an algorithm. O(1), also known as constant time notation, describes an algorithm that takes the same time regardless of the size of the input.

For example, it doesn’t matter if you have an array of 10 elements, or 10,000 elements, it should take the same amount of time.

Definition

An algorithm is said to have a time complexity of O(1) if it takes the same amount of time to execute, regardless of the size of the input. This means that the algorithm’s running time is constant and does not grow with the size of the input.

The number one isn’t a specific number of operations. For example, you won’t see O(5) if there are five steps to the operation. Rather, we’re looking at a constant time, not the actual number of operations. Likewise we’re not measuring the amount of time either. This is because the time an algorithm takes is very dependant upon the speed of the computer (processing, IO, etc).

Examples

Here are some examples of algorithms that have a time complexity of O(1):

• Accessing an element in an array by its index.
• Performing a simple arithmetic operation, such as addition or multiplication.
• Returning a value from a function that does not depend on the input size.

Real-World Examples

Here are some real-world examples of where you might find O(1) algorithms:

• Cache lookup: When you access a webpage, your browser checks its cache to see if it has a copy of the page. This lookup operation is typically O(1), because the browser uses a hash table to store the cache, and looking up an item in a hash table takes constant time.
• Array indexing: When you access an element in an array, the operation takes constant time, regardless of the size of the array. This is because the array is stored in contiguous memory locations, and the index is used to calculate the memory address of the desired element.
• Simple calculations: Performing simple arithmetic operations, such as calculating the area of a rectangle, takes constant time, regardless of the size of the input.

You should note that things like a cache lookup, where you are calculating a hash, might take multiple steps, but it doesn’t matter if you are working on a single element, or 10,000 elements, the time to cache should be approximately the same as it is not dependent upon the number of elements.

A simpler idea is looking at how to find an element within an array. It doesn’t matter, how big your array is, finding the value at a given index is the same.

int a[10];
a[5] = 10;

int b[1000000];
b[5] = 10; // takes the same amount of time as with a

How to Identify O(1) Algorithms

Here are some tips for identifying O(1) algorithms:

• Look for simple operations: If an algorithm only performs simple operations, such as arithmetic or array indexing, it is likely to be O(1).
• Check for hash table lookups: If an algorithm uses a hash table to store data, lookups are typically O(1).
• Watch out for loops: If an algorithm has a loop that depends on the size of the input, it is unlikely to be O(1).
• Watch out for recursion: Like a loop, recursion is dependent upon the size of the input. As such, it will not be an O(1) type of algorithm.

Constant Time Notation: O(1) Style Algorithms was originally found on Access 2 Learn