Constant (O(1))

At a glance: A fixed amount of work or memory is required regardless of how large the input becomes.

Jump to: Time complexity · Space complexity · Try it yourself

Understand the growth

Reading a known array position costs one indexed lookup whether the array has ten elements or ten million. The number of elements stored in the array does not force the lookup to visit preceding entries.

Doubling n does not change the number of primitive operations in the example. For a model that counts one array access as one operation, T(n) = c for a fixed positive constant c.

What the constant bound actually promises

An O(1) claim refers to a specific operation under a specific cost model. Array indexing can be constant because the address of element i is computed from the array base and the fixed-size element width. No earlier element has to be inspected. For a nonempty array, returning values[0] performs one access no matter how long the array becomes. The access itself is even Θ(1) in the usual RAM model.

The claim does not include work performed before the index is known. Searching an unsorted array for the desired element takes up to n comparisons; looking it up afterward is still O(1), but the complete operation is O(n). Likewise, list.Count can be constant while building the list is not. Separate the cost of obtaining a data structure from the cost of querying it.

The cost model matters. Fixed-width integer addition is usually counted as one step, but arbitrary-precision integers become more expensive as their bit length grows. Constant asymptotic work does not imply identical microseconds: cache misses, bounds checks and contention can change observed latency. It only means the modeled number of steps does not grow with n.

Worked example

For n = 8, n = 8,192 and n = 8,192,000, reading values[0] still performs a single lookup. This does not mean the three runs have identical measured latency: cache locality, bounds checks, and hardware may affect real timings.

Trace one access versus a search

Imagine three arrays containing 8, 8,192 and 8,192,000 integers. Reading index 0 performs one indexed read in each case. If instead you need to find the first occurrence of the number 7, the index is unknown: an unsuccessful linear scan examines all 8, all 8,192 or all 8,192,000 items. Both pieces of code may end with values[index], yet the end-to-end complexity is different.

For a hash table, average lookup is often expected O(1) under an adequate hash distribution and suitable load factor; collisions or a hostile input can violate a simplistic worst-case O(1) claim. Another constant-cost example is swapping two existing scalar variables, provided their values have fixed size.

Time complexity

Representative time example: Accessing one known index.

The C# indexed access assumes an actual array, a valid index and a constant-cost element read. Bounds checking still takes constant work. If the index must first be found by scanning, that search is not constant time. Hash-table lookup is often expected constant time on average, but collisions and adversarial keys can worsen the worst case. This is why it matters whether the claim describes a specific step or the whole operation.

Trace the operation, not the line count

For int first = values[0], count one bounds check and one indexed load in a simple model. Neither requires a loop over the array. The statement assumes a valid, already available array; handling an invalid index by throwing an exception is a separate control-flow path, still not a scan of n elements.

Compare values[0] with a linked-list operation that reaches position i by following i pointers. The latter requires O(i) work and O(n) in the worst case if i can approach the end. Similarly, asking a database for a single row does not prove O(1): the query may involve an index traversal, network latency, or a full table scan. Identify the underlying data structure before transferring an O(1) label from one API to another.

C#

C# | Constant.cs

int first = values[0]; // assuming values is nonempty

C++

C++ | constant.cpp

#include <vector>

int first = values.at(0); // std::vector<int> values; requires nonempty input

Analysis: Direct indexing into an array uses constant worst-case time for the lookup.

The C++ version illustrates the same operation. The container, compiler and any functions called by the example still matter when analyzing a complete program.

Space complexity

Representative memory example: A handful of scalar variables.

A running sum can scan every item while retaining only its accumulator and loop variable. The number of input values grows, but these few local values do not. That makes the algorithm O(n) in time and O(1) in auxiliary space. The input array itself occupies O(n) storage if included in total space; excluding it is a deliberate accounting choice, not a contradiction.

Constant workspace during nonconstant work

The accumulator example retains one running total and one current item, independent of the number of elements. At every moment it uses a bounded number of extra fixed-width values: Θ(1) auxiliary space. Yet reading the entire array takes Θ(n) time. This is the clearest demonstration that time and space cannot be inferred from each other.

If the input array has n integers, its storage contributes Θ(n) to total space; the few local variables do not erase that input cost. Conversely, copying the array would create another Θ(n) buffer, changing the auxiliary bound. A recursive traversal that keeps one stack frame per input element may also consume Θ(n) extra space even if every frame contains just one index. Ask which memory remains live simultaneously, not how many assignments the function has performed.

C#

C# | Constant.cs

int total = 0;
foreach (int value in values) total += value;

C++

C++ | constant.cpp

int sum = 0;
for (int value : values) sum += value; // constant extra storage

Analysis: The accumulator adds O(1) auxiliary space even though the loop takes O(n) time.

The stated bound describes stored elements and active call frames. Actual byte counts also depend on runtime, allocator and element representation.

Recognize constant behavior in real code

Common constant-time operations include reading or writing a valid array index, checking a stored collection length, incrementing a fixed-width counter, and swapping two existing values. These are operations, not a guarantee for the surrounding algorithm. A fixed loop that runs exactly ten times is still O(1) when ten never depends on input size; a loop that runs n / 10 times is O(n), despite the smaller constant.

Distinguish worst-case guarantees from expectations: direct array access has a straightforward worst-case constant bound under the usual model, while hashing usually needs assumptions about collision behavior. Also distinguish constant extra memory from constant total memory. A function may consume an existing million-element input with only two counters. This is not a contradiction; it is careful accounting.

Practical example: a game’s inventory slots

A fixed-size array of inventory slots lets a game read slot 12 directly, provided that slot exists. Enlarging the inventory does not make that indexed read iterate through earlier slots. However, a UI action saying “find the first empty slot” generally requires scanning until an empty entry is found, which is O(n) in the worst case. A dictionary mapping item IDs to slots may improve expected lookup time, but adds storage, maintenance cost and collision assumptions.

When reviewing a method called GetItem, don’t infer its complexity from the name. Check whether its argument is an index, an item identifier, or a predicate that requires searching. Also check whether the method constructs an item list before returning a single entry. That preparation belongs in the total cost.

Common mistake

Watch out: Do not call an algorithm O(1) merely because one statement is O(1). Allocating an n-element array, copying its contents, or searching for a location before the access changes the complete cost.

Try it yourself

Implement a sum of an array and classify its time and auxiliary space separately. Explain why the answers differ.

1. Define exactly what n represents.
2. Count the key operation in the best and worst case where relevant.
3. Count the maximum simultaneously live memory.
4. Check your prediction in the Big O explorer.

Continue learning

Big O overview · Time complexity · Space complexity · Compare classes