O(1) vs O(n): Constant Time vs Linear Time, Explained

Most complexity questions in an interview come down to one distinction, asked about one line at a time: does this step cost the same no matter how big the input is, or does it touch every item? That is O(1) versus O(n), constant time versus linear time. Get it right line by line and the bigger classes follow, because they are mostly these two nested or repeated. This article makes the distinction measurable by counting instead of timing.

The problem it solves

"This code is slow" is not actionable. "This line is O(n), and it runs inside a loop" is. Big-O describes how the work grows as the input grows, ignoring the machine and the constant factors; the Big-O definition article covers the formal side. Here the question is practical: for a given line, which is it?

• O(1): the amount of work does not depend on n. Reading nums[0], or nums[-1], or len(nums).
• O(n): the work grows in step with n. Summing a list, finding its maximum, or searching an unsorted list for a value that may not be there.

The intuition

Ask one question of each operation: if the input doubled, would this do more work? If not, it is O(1). If it would do roughly double, it is O(n).

A few cases trip people up:

• Early exit does not make a scan O(1). A search that stops at the first match is O(1) in the best case, but Big-O is usually quoted for the worst case: the item is last, or absent, and every element is read.
• Two passes are still O(n). Finding the minimum, then the maximum, reads 2n elements. Constants drop, so 2n is O(n). Only a loop inside a loop multiplies.
• A loop with a fixed bound is O(1). Summing the first ten items costs ten reads whether the list holds 20 items or 20 million.
• O(1) does not mean fast. It means "does not grow with n". A constant-time step can still be expensive, and hashing a long string costs time proportional to the string, not to the size of the table.

The same split applies to memory. Reversing a list in place needs O(1) extra space: a couple of indices. Building a reversed copy needs O(n) extra space: a second list as long as the first.

Watch it run

The animation puts one list of eight numbers in two lanes with two jobs: read one slot, or look for a value that could be anywhere. In the top lane, nums[0] is one address calculation, and the other seven values are never even touched; its counter stops at 1. The bottom lane looks for 42. Seven is not 42, so the scan has no choice but to keep walking; then 3, 9, 1, 8, 5 and 6, each read and ruled out while the counter climbs. It finds 42, but only after touching every one of the eight items. The closing frame makes the point with growth rather than speed: double the list and the top lane still does one operation, while the bottom does sixteen. That gap is O(1) versus O(n).

The code

A list wrapper that counts element reads, so the numbers never depend on the machine. Four functions, three list sizes:

import random
import timeit
import tracemalloc

class Steps:
    """Count element reads instead of timing them, so the numbers never depend on the machine."""
    def __init__(self, items):
        self.items, self.reads = items, 0
    def __getitem__(self, i):
        self.reads += 1
        return self.items[i]
    def __len__(self):
        return len(self.items)              # a stored count: no element is read

def first_item(nums):
    return nums[0]                          # one read, any size

def contains(nums, target):
    for i in range(len(nums)):              # up to n reads
        if nums[i] == target:
            return True
    return False

def min_and_max(nums):
    lo = min(nums[i] for i in range(len(nums)))
    hi = max(nums[i] for i in range(len(nums)))
    return lo, hi                           # two passes: 2n reads, still O(n)

def first_ten_sum(nums):
    return sum(nums[i] for i in range(min(10, len(nums))))   # capped: O(1)

for n in (1_000, 2_000, 4_000):
    row = []
    for fn, args in ((first_item, ()), (contains, (-1,)), (min_and_max, ()), (first_ten_sum, ())):
        s = Steps(list(range(n)))
        fn(s, *args)
        row.append(s.reads)
    print(n, row)
# 1000 [1, 1000, 2000, 10]
# 2000 [1, 2000, 4000, 10]
# 4000 [1, 4000, 8000, 10]

Each doubling of n doubles the two linear columns and leaves the other two alone. That doubling test also works on built-ins whose insides you cannot count. With ten times the data, x in a list takes about ten times as long, while x in a set, len and indexing do not move. Timings print as comparisons with a wide margin, so they hold on any machine. Memory gets the same treatment with tracemalloc:

def best_time(stmt, n, number):
    data = list(range(n))
    env = {"data": data, "lookup": set(data), "x": -1}
    return min(timeit.repeat(stmt, globals=env, number=number, repeat=5))

for stmt, number in (("x in data", 20), ("x in lookup", 100_000), ("len(data)", 100_000), ("data[-1]", 100_000)):
    ratio = best_time(stmt, 1_000_000, number) / best_time(stmt, 100_000, number)
    print(f"{stmt:<12} 10x the data:", "about 10x the time" if ratio > 5 else "about the same")
# x in data    10x the data: about 10x the time
# x in lookup  10x the data: about the same
# len(data)    10x the data: about the same
# data[-1]     10x the data: about the same

def extra_memory(fn, n):
    data = list(range(n))
    tracemalloc.start()
    fn(data)
    peak = tracemalloc.get_traced_memory()[1]
    tracemalloc.stop()
    return peak

print(extra_memory(lambda a: a.reverse(), 100_000) < 1_000)          # True: O(1) extra space
print(extra_memory(lambda a: a[::-1], 100_000) > 8 * 100_000)        # True: O(n), a full copy

The seeded check covers 500 random lists. Every function must give the same answer as Python's built-ins, the read counts must match the exact formulas (index plus one for a hit, n for a miss, 2n, ten or fewer, one), and a full scan of a doubled list must read exactly twice as much:

ok = True
for seed in range(500):
    r = random.Random(seed)
    nums = [r.randint(-50, 50) for _ in range(r.randint(1, 300))]
    target = r.randint(-60, 60)
    s = Steps(nums)
    found = contains(s, target)
    ok &= found == (target in nums)
    ok &= s.reads == (nums.index(target) + 1 if found else len(nums))
    s = Steps(nums)
    ok &= min_and_max(s) == (min(nums), max(nums)) and s.reads == 2 * len(nums)
    s = Steps(nums)
    ok &= first_ten_sum(s) == sum(nums[:10]) and s.reads == min(10, len(nums))
    s = Steps(nums)
    ok &= first_item(s) == nums[0] and s.reads == 1
    big, small = Steps(nums * 2), Steps(nums)               # doubling n doubles a full scan
    contains(big, 999), contains(small, 999)
    ok &= big.reads == 2 * small.reads
print(ok)                                                    # True

The complexity

• O(1): indexing, len, append (amortised), set and dict membership (average), reading a field.
• O(n): in and index on a list, sum, min, max, copying, insert(0, x), pop(0).
• Combining: sequential steps add, so O(n) + O(n) is O(n); nested steps multiply, so O(n) inside a loop of n is O(n²).

The Python cheat sheet lists these per type, and the Big-O cheat sheet puts them beside the other classes.

Where it goes wrong

• Calling an early-exit scan O(1). Quote the worst case unless asked otherwise.
• Calling 2n O(2n). Drop the constant.
• Hiding O(n) inside one line. if x in some_list in a loop is a nested loop; the O(n²) article collects these.
• Forgetting space. A slice, sorted() or a list comprehension allocates O(n).

When it shows up in interviews

Constantly, as the first step of every complexity analysis: "what is the cost of this line?". It also drives the most common optimisation, swapping an O(n) list search for an O(1) average set or dict lookup, as in two sum. The broader map is in complexity classes.

How to say it in an interview

"O(1) means the work doesn't grow with the input: indexing, len, or a hash lookup on average. O(n) means it grows in step with n: a scan, a sum, a copy. My test is to imagine the input doubling: if the work doubles, it's linear. Early exit doesn't change the worst case, two sequential passes are still O(n), and a loop with a fixed bound is O(1). Space works the same way: reversing in place is O(1) extra, building a copy is O(n)."