What constant time means
An operation runs in constant time, written O(1), when the number of steps it takes does not depend on the size of the input. Give a function an array of 10 elements or an array of a million, and it does the same amount of work.
The "1" does not mean one step. It means a fixed number of steps that does not grow with the input. A function that does 3 steps and a function that does 300 steps are both O(1) as long as neither count changes when the input gets bigger.
Take reading the first element of an array:
function first(nums: number[]): number {
return nums[0];
}
const big = Array.from({ length: 1000000 }, (_, i) => i);
console.log(first([5, 6, 7, 8, 9])); // 5
console.log(first(big)); // 0
An array stores its elements so that the one at position i can be reached directly, without looking at the elements before it. The call on the million-element array does the same work as the call on the five-element one.
Common O(1) operations in TypeScript
- Arithmetic and comparisons.
a + b,n % 2 === 0andx < yon numbers take a fixed amount of work. - Reading or writing an array element by index.
nums[i]andnums[i] = valuedon't depend onnums.length. - Reading the length.
nums.lengthis a stored property, not something computed by counting. - Adding or removing at the end.
pushandpoptake constant time on average. Occasionally an array has to grow its storage, but spread over many calls the cost per call stays constant. - Looking up an object property.
user.nameanduser["age"]don't search through the other properties. - Using a
Mapor aSet.get,set,hasanddeletetake constant time on average, however many entries there are.
const stack: number[] = [];
stack.push(1);
stack.push(2);
console.log(stack.pop(), stack.length); // 2 1
const ages = new Map<string, number>();
ages.set("Ana", 31);
console.log(ages.get("Ana"), ages.has("Bo")); // 31 false
const seen = new Set<number>([1, 2, 3]);
console.log(seen.has(2), seen.has(9)); // true false
The word "average" for hash-based structures matters. Hash lookups are constant time when keys spread out well, which is the normal case. They are not a guarantee for every possible key set, but for the purposes of this course you can treat Map and Set operations as O(1).
Counting steps
You can see the difference between constant and linear time by counting. This function reports how many steps a constant-time part and a loop-based part take for different input sizes:
function countSteps(n: number): [number, number] {
let constantSteps = 0;
let linearSteps = 0;
constantSteps++;
for (let i = 0; i < n; i++) {
linearSteps++;
}
return [constantSteps, linearSteps];
}
console.log(countSteps(10)); // [ 1, 10 ]
console.log(countSteps(1000)); // [ 1, 1000 ]
The constant part stays at 1 whatever n is, while the loop grows with n. In Big O terms the first is O(1) and the second is O(n).
Constant time can still contain loops
A loop does not make code linear by itself. What matters is how many times it runs. If the number of iterations is fixed, the code is still O(1):
function sumFirstThree(nums: number[]): number {
let total = 0;
for (let i = 0; i < 3; i++) {
total += nums[i];
}
return total;
}
console.log(sumFirstThree([5, 6, 7, 8, 9])); // 18
The loop always runs exactly three times, whether nums has 3 elements or 3 million. This function is O(1). Replacing 3 with nums.length would make it O(n).
The same rule applies to a loop that always runs 1000 times. A thousand steps is a lot, but it is a fixed amount of work. Big O describes how the cost grows, not how large it is today.
Because constants are dropped, O(2) and O(500) are both written O(1). If a function does three constant-time operations one after another, the total is still O(1).
Gotchas
- Constant does not mean fast. A function that always does a million steps is
O(1). Constant time is about growth, so for small inputs a simpleO(n)approach can beat a complicatedO(1)one. - Check what hides behind a method call.
nums.lengthis constant, butnums.includes(x),nums.indexOf(x)andnums.slice()look at many elements. Writing one short line does not mean one step. - Out-of-range reads are also constant. Reading
nums[0]from an empty array doesn't fail in TypeScript. It givesundefined, and the type system still saysnumber, because types are erased when the code is compiled and never checked at run time. - Input size must be what grows. A function that takes a single number
nand computesn % 2 === 0isO(1). The size of the number does not matter here, because arithmetic on a regularnumbertakes a fixed time.
Why this matters for the chapter
Constant time is the best case you can ask for, and it is the baseline you compare other complexities against. A common goal in the lessons ahead is to turn repeated O(n) work into O(1) lookups, for example by putting values into a Set once instead of scanning an array again for each query.
Key takeaways
O(1)means the number of steps doesn't grow with the input size.- Index access,
length,push,pop, andMapandSetoperations are constant time (the last group on average). - A loop with a fixed number of iterations is still
O(1). - Constants are dropped, so
O(1)says how the cost grows, not how big it is.