What does O(n) mean, and why do we ignore constants such as in 3n + 10?

O(n) means the number of steps grows in proportion to the input size n: double n and the work roughly doubles. We drop constants and smaller terms because Big-O describes the shape of the growth for large n. For 3n + 10, the 10 stops mattering as n grows, and the 3 only changes the slope, not the fact that the growth is a straight line. So 3n + 10 is O(n), and n² + n is O(n²). Constants still matter in practice, but they are a separate question from how the algorithm scales.

What is the time complexity of a loop where the inner loop runs from i + 1 to n, and why?

The inner body runs n - 1 times for i = 0, n - 2 times for i = 1, and so on down to 1. That sum is n(n - 1) / 2, which is n²/2 - n/2. Drop the constant 1/2 and the smaller term and it is O(n²). Memory is O(1) because only a few counters are kept. This is the shape of "compare every pair", such as the brute-force duplicate check.

You must check whether a list of n ids has a duplicate. Compare a nested-loop solution with a hash set solution.

Nested loops compare every pair: O(n²) time and O(1) extra memory. A hash set remembers the ids seen so far, and checking or adding an id takes O(1) on average, so one pass is O(n) time with O(n) extra memory. The hash set trades memory for speed. If memory is very tight and n is small, nested loops are fine. If you may also sort the data, sorting first and comparing neighbours gives O(n log n) time and little extra memory, a third point on the trade-off.

Why is appending to a dynamic array (a list or vector) called amortised O(1) when a single append can cost O(n)?

When the array is full it allocates a bigger block, usually double the size, and copies every item over. That one append costs O(n). But the doubling makes those expensive appends rare: over n appends the total copying is about n + n/2 + n/4 + ..., which is under 2n. Spread across n appends, the average is O(1) per append. Amortised means this average over a sequence of operations, not an average over random inputs. The worst single operation is still O(n).

Why is binary search O(log n)?

Each comparison throws away half of the remaining items, so after k steps about n / 2^k items are left. The search ends when that reaches 1, which happens when k is about log2 of n. For one million items that is about 20 comparisons. Memory is O(1) for the loop version, and O(log n) for the recursive version because of the call stack.

Time and Space Complexity (Big-O)

beginner · 30 min · Asked often · Last reviewed 29 Oct 2026 · by TheLearningLoop Team

Key takeaways

Big-O describes how the number of steps (time) or the amount of memory (space) grows as the input size n grows, not how many seconds a program takes.
Drop constants and smaller terms. 3n + 10 is O(n), and n² + n is O(n²), because only the fastest-growing part matters for large n.
The common classes, from best to worst, are O(1), O(log n), O(n), O(n log n), O(n²) and O(2ⁿ). Know an example of each.
Many problems trade one cost for the other. A hash set can turn O(n²) time into O(n) time by spending O(n) memory.

New to this topic? Read the overview first: Data Structures & Algorithms: The Big Picture

When to use Big-O analysis

Use Big-O when you want to:

Compare two solutions before you write them, for example nested loops against a hash set.
Predict whether code will cope with bigger input: "this works for 1,000 items, but will it work for a million?"
Explain your solution in an interview: every answer should end with its time and memory cost.
Spot the slow part of a design, such as a query that scans a whole table for every request.

Use something else when:

You need the real running time on real hardware: measure it with a benchmark or a profiler. Big-O ignores constants, caches and the network.
The input is always tiny (a dozen items). Then the simplest code wins, whatever its Big-O.
You care about one slow request rather than growth: look at latency percentiles such as p99 instead.

There is nothing to import. Big-O is a way of describing code, not a library. Every language's documentation quotes it for its built-in lists, maps and sorts (see the real-world section).

How Big-O works

Big-O describes how the work (time) or the memory (space) of an algorithm grows as the input size, written n, grows. It does not measure seconds. It counts steps, such as comparisons, so the answer is the same on a laptop and a phone.

Keep only the part that grows fastest, and ignore constant factors. 3n + 10 is O(n). n² + n is O(n²).

Why drop the rest? For a large n, the fastest-growing term swamps the others. At n = 1,000,000, n² is a trillion while n is a million, so the extra n changes almost nothing.

Here are the classes you will meet, from best to worst:

O(1), constant. The work does not depend on n: reading array[i].
O(log n), logarithmic. The problem is halved each step: binary search.
O(n), linear. One pass over the data: summing a list.
O(n log n), linearithmic. Halve the problem, but do a pass at each level: merge sort.
O(n²), quadratic. A loop inside a loop over the same data: comparing every pair.
O(2ⁿ), exponential. The work doubles with every extra item: trying every subset. Only usable for tiny n.

Space complexity is the same idea for memory. It counts the extra memory the algorithm needs beyond its input, including the call stack of a recursive function.

Try it

Pick an input size, press Run, then step through. Each frame doubles n and shows how many steps each growth rate needs.

How work grows with input size

Step 1 of 5 · Press Space to play, arrow keys to step

Examples:

Input size n = 1

O(1)

Read array[i]

O(log n)

Binary search

O(n)

Loop over every item

O(n log n)

Merge sort

O(n²)

Compare every pair

O(2ⁿ)

Try every subset

Start with a single item. Every growth rate does about the same work here. Press Play and watch what happens as n doubles.

input size n:: 1
linear steps:: 1
quadratic steps:: 1
exponential steps:: 2

A step is one basic operation, such as one comparison. Bars are drawn to scale against the biggest non-exponential count; a red bar is off the chart.

Speed

Things to try:

Small (8): at n = 8 the six classes take 1, 3, 8, 24, 64 and 256 steps. The first five are small, but exponential is already the biggest, and its red bar means it no longer fits the chart.
Medium (64): now quadratic takes 4,096 steps against 64 for linear and 6 for logarithmic. Watch the logarithmic bar barely move as n doubles.
Large (1,000): quadratic is 1,000,000 steps, while binary search needs 10. Exponential has been off the chart (the red bar) since about n = 8, and by n = 64 it cannot even be counted.

Big-O operations: working out the complexity

You do not need calculus. Read the code and apply a few rules.

Steps one after another add. A loop of n steps followed by a loop of n steps is n + n = 2n, which is O(n).
Steps inside steps multiply. A loop of n containing a loop of n is n × n, which is O(n²).
Halving gives a logarithm. If each step cuts the remaining work in half, the number of steps is about log2 n, which is O(log n).
Different inputs, different letters. Looping over list a and then list b is O(a + b), and nested is O(a × b). Do not call both n.
Recursion: count the calls and the work per call. A function that calls itself once with n - 1 does n calls. One that calls itself twice with n - 1 does about 2ⁿ.
Space: count what you allocate. A new list of n items is O(n) memory. A recursion that goes n calls deep uses O(n) stack.

Three more ideas that interviewers ask about:

Worst, best and average case. Quoted Big-O is usually the worst case. Searching a list for an item is O(1) if it is first, but O(n) if it is last or missing.
Amortised cost. Appending to a dynamic array occasionally copies everything (O(n)), but doubling the capacity makes those copies rare, so the average append is O(1).
Time against space. You can often buy speed with memory. Interview fact: a hash set turns an O(n²) duplicate check into O(n), at the price of O(n) extra memory.

Big-O time complexity

How many steps each class needs as n grows, and a familiar example of each.

Class	`n = 10`	`n = 1,000`	`n = 1,000,000`	Example
O(1)	1	1	1	Read `array[i]`, push on a stack
O(log n)	about 4	about 10	about 20	Binary search
O(n)	10	1,000	1,000,000	Find the largest item
O(n log n)	about 40	about 10,000	about 20,000,000	Merge sort
O(n²)	100	1,000,000	1,000,000,000,000	Compare every pair
O(2ⁿ)	1,024	more than the atoms in the universe	not possible	Try every subset

A rough rule of thumb is that a computer does about 100 million simple steps a second. So O(n²) is comfortable up to a few thousand items, O(n log n) up to millions, and O(2ⁿ) only up to about 25 items. If an interview problem allows n up to 100,000, an O(n²) answer will probably be too slow.

Big-O vs other ways to compare code

Big-O is one of several tools. n is the input size.

What you want to know	Big-O	Benchmark (timing it)	Counting exact steps	Profiler
Which of two designs scales better	Yes, before writing it	Only after writing both	Possible but tedious	No
Real seconds on real hardware	No	Yes	No	Yes
Which function is the slow one	Only roughly	Slow to narrow down	No	Yes
Effect of caches, network, constants	No	Yes	No	Yes
Works in an interview, on paper	Yes	No	Sometimes	No

Big-O wins when you are choosing a design on paper. It never replaces measuring: two algorithms with the same Big-O can differ by 10 times in real time.

How to explain Big-O in an interview

State the variable. Say what n is: "n is the number of ids", or "a is the rows and b is the columns".
Give both costs, every time. "This is O(n) time and O(1) extra memory." Mention the recursion stack if there is one.
Name the worst case, then the typical case when they differ: "a hash set is O(1) on average, O(n) in the worst case."
Show the trade-off. "I can get O(n) time with a set, or O(1) memory with nested loops. Given 100,000 ids I would take the set."
Say why, not just what. "It is O(n²) because the inner loop runs about n times for each of the n outer iterations."

Where you meet Big-O in real systems

Big-O decides which designs survive when the data grows. Here are three examples drawn out, the first with code you can run, then more.

Example 1: Finding duplicate ids in an import

A company imports a file of 2,000 customer ids and must reject it if any id appears twice. The obvious answer compares every id with every other: 1,999,000 comparisons for 2,000 ids. With 200,000 ids that would be about 20 billion. Remembering the ids already seen in a set does one lookup per id instead: 2,000 steps for 2,000 ids. Open the example below to see the picture and the code.

Code: duplicate check with nested loops and with a hash setTime O(n²) vs O(n)Memory O(1) vs O(n)

Nested loops compare every pair, so the work is about n squared. A hash set looks at each id once, so the work is about n. At 2,000 ids that is 1,999,000 comparisons against 2,000 set inserts.

Run with 2,000 distinct ids (0, 3, 6, ...), all five versions report the same result: no duplicate, 1,999,000 comparisons for the nested loops and 2,000 inserts for the set. The Java code needs Java 16 or newer for record. The C++ code builds with -std=c++17.

def has_duplicate_nested(ids):
    """Check for a repeated id by comparing every pair. Returns (found, comparisons).

    Each id is compared with every id after it, so with n ids there are up to
    n * (n - 1) / 2 comparisons. Doubling n roughly quadruples the work.

    Time:   O(n^2). Two nested loops over the same list.
    Memory: O(1). Only a few counters, whatever the size of `ids`.
    """
    comparisons = 0
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            comparisons += 1
            if ids[i] == ids[j]:
                return True, comparisons
    return False, comparisons


def has_duplicate_set(ids):
    """Check for a repeated id by remembering the ids seen so far. Returns (found, inserts).

    A set answers "have I seen this id?" in constant time on average, so each id is
    handled once. Doubling n roughly doubles the work. The price is extra memory.

    Time:   O(n) on average. One set lookup and one insert per id.
    Memory: O(n). In the worst case the set holds every id.
    """
    seen = set()
    inserts = 0
    for x in ids:
        if x in seen:                 # average O(1) lookup
            return True, inserts
        seen.add(x)                   # average O(1) insert
        inserts += 1
    return False, inserts

Example 2: A database index against a full table scan

A table has 1,000,000 rows and a query asks for one user by id. Without an index, the database reads rows one by one: O(n), up to a million rows. With an index on the id, the database narrows the search by repeatedly cutting the range, much like binary search, and reaches the row in about 20 steps: O(log n). That is why adding an index to a slow query can turn seconds into milliseconds.

Each step halves the range that could hold the row. After about 20 halvings only one row is left. Real database indexes are usually trees with many branches, but the effect is the same: logarithmic, not linear.

Example 3: Sorting a million rows against comparing every pair

Sorting a million records with a good algorithm takes about n log n, or 20 million steps, which finishes in well under a second. Comparing every record with every other takes n², or a trillion steps, which takes hours. Both look at "all the data", but the growth rate decides which one is usable.

At 1,000 items both approaches are instant. At a million items the O(n log n) approach needs about 20 million steps and the O(n²) approach needs a trillion.

More real-world scenarios

4. Autocomplete suggestions

A search box suggests words as you type. Scanning every stored word for each key press is O(n). Systems use a prefix structure (a trie) so the cost depends on how many letters you typed, not on how many words exist.

5. Collision checks in a game

A game with 1,000 moving objects that checks every pair does about half a million checks per frame, and at 60 frames a second that is too much. Engines split the world into a grid and only compare objects in the same or nearby cells, which brings the work close to O(n).

6. Ranking a social feed

Sorting every post a user could see is O(n log n). When the app only needs the top 20, it keeps a small heap of 20 items instead, which is O(n log k) with k = 20, and uses far less memory.

7. Memory limits in a cache

A cache that keeps every computed result grows as O(n) in memory and eventually runs out. Designers add an eviction rule (such as least recently used) so memory stays bounded, accepting that some answers must be recomputed.

8. App start-up and memory on a phone

Loading every image of a photo gallery into memory at once uses O(n) memory and can crash a phone. Gallery apps load only the screens near the visible area, so the memory used stays close to constant however many photos there are.

9. Searching logs

Running grep over a log file reads every line: O(n). When engineers search the same logs constantly, a search system builds an index (a map from each word to the lines containing it), which costs memory and build time but makes each query much faster.

10. Cloud cost and capacity planning

If a nightly job is O(n²) in the number of customers, doubling the customer base quadruples the compute bill and run time. Teams use Big-O to spot which jobs will not survive growth before the bill or the deadline shows it.

Language standard libraries

Each language's documentation or standard describes costs for its built-in structures. Use these as a reference when you choose between them.

Language	Structure or class	What it is under the hood	Notes
Java	`ArrayList`, `HashMap`, `Collections.sort`	Resizable array, hash table, merge-based sort	`ArrayList.get` is O(1) and `add` is amortised O(1). `HashMap` lookups are O(1) on average. Sorting objects is O(n log n).
C++	`std::vector`, `std::unordered_map`, `std::map`, `std::sort`	Resizable array, hash table, balanced tree, sort	`push_back` is amortised O(1). `unordered_map` is O(1) on average and O(n) worst case. `map` is O(log n). `std::sort` is O(n log n).
C#	`List<T>`, `Dictionary<K,V>`, `List<T>.Sort`	Resizable array, hash table, introspective sort	`Add` is amortised O(1). `Dictionary` lookups are O(1) on average. `Sort` is O(n log n).
Rust	`Vec`, `HashMap`, `BTreeMap`, `slice::sort`	Resizable array, hash table, B-tree, stable sort	`push` is amortised O(1). `HashMap` is O(1) expected. `BTreeMap` is O(log n). `sort` is O(n log n).
Python	`list`, `dict`, `set`, `list.sort`	Dynamic array, hash table, hash table, Timsort	`append` is amortised O(1). `dict` and `set` lookups are O(1) on average. `x in list` is O(n). Sorting is O(n log n).
Go	Slices, `map`, `sort.Slice`	Slice over an array, hash table, sort	`append` is amortised O(1). `map` lookups are O(1) on average. Sorting is O(n log n).
JavaScript	`Array`, `Map`, `Set`, `Array.prototype.sort`	Engine-defined array, hash-based collections	`push` is amortised O(1) in common engines. `Map` and `Set` are specified to be sub-linear on average. `sort` is stable and O(n log n) in common engines.
Kotlin	`ArrayList`, `HashMap`, `sortedBy`	The Java collections on the JVM	The same costs as Java. `sortedBy` returns a new sorted list, so it also uses O(n) extra memory.

The pattern: every language gives you the same three trade-offs. A dynamic array for fast reads by position, a hash table for fast lookups by key, and a sort at O(n log n). The skill is picking the one whose cost matches your question.

The takeaway

Whenever a system must keep working as its data grows, look for the growth rate: an index to make lookups O(log n), a set to avoid O(n²), a heap to avoid sorting everything. When the data is small and fixed, the simplest code usually wins, and engineers measure instead of calculating.

Interview questions

Try answering out loud before you reveal hints. Interviewers care about how you reason, not just the final answer.

1.
What does O(n) mean, and why do we ignore constants such as in 3n + 10?
easy
2.
What is the time complexity of a loop where the inner loop runs from i + 1 to n, and why?
easy
3.
You must check whether a list of n ids has a duplicate. Compare a nested-loop solution with a hash set solution.
medium
4.
Why is appending to a dynamic array (a list or vector) called amortised O(1) when a single append can cost O(n)?
medium
5.
Why is binary search O(log n)?
easy

Finished this lesson?

Progress is saved on this device. Create a free account to keep it everywhere.

Arrays and Strings

Topics:Big OTime complexitySpace complexityGrowth rateAsymptotic analysisAmortised