vizlearn
Home / Algorithms

Big-O Notation and Time Complexity

Algorithms & Data StructuresBy Updated

How does an algorithm's cost grow as the input grows? Race the six complexity classes against each other and watch the ones that look fine at n=10 become impossible at n=1000.

Controls

input size n20

Show curves

Growth Curves

step 0

Insight

Big-O describes how work grows with input size — it ignores constants and small terms, because at scale only the shape of growth matters.

Where VizLearn's algorithms land

O(log n) — binary search
O(n) — linear search, counting sort
O(n log n) — merge sort, quick sort
O(n²) — bubble, insertion, selection
O(2ⁿ) — naive recursive Fibonacci

Overview

Big-O describes an upper bound on how an algorithm's time or memory use grows with input size n. It ignores constant factors and lower-order terms: 3n + 50 is O(n). It helps compare growth, but does not predict exact run time on a particular machine.

Quick Context

The six classes you will encounter most often are O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic and O(2ⁿ) exponential.

Why Ignore the Constants?

Because hardware changes and growth does not. A machine twice as fast halves every constant, but an O(n²) algorithm is still O(n²) — double the input and you quadruple the work, forever.

Slide n and watch the table. At n = 10 every row looks affordable. By n = 1000 the quadratic column is a million operations and the exponential column has left the universe behind.

The Six Classes You Will Meet

  • O(1) constant — cost stays bounded as n grows. Array index lookup and stack push are typical; hash-table lookup is expected O(1), not a worst-case guarantee.
  • O(log n) logarithmic — each step halves the problem. Binary search, balanced tree operations. Doubling n adds just one step.
  • O(n) linear — touch every item once. Linear search, summing an array.
  • O(n log n) — common for efficient comparison sorts. Merge sort and heapsort have this worst-case bound; quicksort is O(n log n) on average but O(n²) in the worst case.
  • O(n²) quadratic — often comes from nested loops over the data. Bubble, insertion and selection sort have quadratic worst cases; simple versions can still suit small or nearly sorted inputs.
  • O(2ⁿ) exponential — every extra element doubles the work. Naive recursive Fibonacci, brute-force subsets. Intractable beyond roughly n = 40.

Compare the growth rates

ComplexityNamen = 10n = 1,000n = 1,000,000
O(1)Constant111
O(log n)Logarithmic31020
O(n)Linear101,0001,000,000
O(n log n)Linearithmic3010,00020,000,000
O(n²)Quadratic1001,000,00010¹²
O(2ⁿ)Exponential1,024astronomicalimpossible

The table shows growth, not wall-clock time: actual duration depends on the operation, implementation and hardware. At n = 1,000,000, the listed O(n log n) model is about 20 million units of work, while the quadratic model is 10¹². Their ratio illustrates why input growth can dominate constant-factor tuning.

Reading complexity from code

The rules are mechanical once you see them.

A loop over the input is O(n).

Nested loops multiply. Two loops over n is O(n²); three is O(n³).

Sequential loops add, and the larger term wins: O(n) + O(n²) = O(n²).

Halving the search space each step is O(log n). Binary search on a million items takes 20 steps, because 2²⁰ ≈ 1,000,000.

Dictionary and set lookups are expected O(1). Hash collisions can make a lookup slower, so this is not a worst-case guarantee.

# O(n^2) - for each item, scan the whole list
for a in items:
    if a in other_list:      # this scan is O(n)
        ...

# O(n) - build a set once, then constant-time lookups
other = set(other_list)
for a in items:
        if a in other:           # expected O(1)
        ...

That transformation — replacing a repeated scan with a pre-built set or dictionary — is the most common and most effective optimisation in everyday code, and it usually makes the code shorter as well.

Things to try with Big-O Notation and Time Complexity

  1. Start at n = 10. Every curve is bunched together — at small inputs, complexity genuinely does not matter and the constants dominate.
  2. Slide to n = 60. The exponential curve leaves the chart almost immediately, then the quadratic. The separation is the entire point of the notation.

Space complexity

The same notation applies to memory, and it is frequently the binding constraint.

ApproachTimeSpace
Sort in placeO(n log n)O(1) extra
Merge sortO(n log n)O(n) extra
Recursion depth d—O(d) stack
Memoised FibonacciO(n) timeO(n) extra

Recursion's space cost is easy to overlook: each active call holds a frame, so depth n uses O(n) stack space. Python limits recursion depth; the configured limit varies by environment. Deep input may need an iterative solution or an explicit stack.

Memoisation is a time-for-space trade: naive recursive Fibonacci takes O(2ⁿ) time and O(n) stack space, while memoised Fibonacci takes O(n) time and O(n) total extra space. The improvement comes from computing each state once.

Sources and next steps

Run it in Python

Five complexity classes, each with its operations counted rather than argued about, at three input sizes. The last block shows an O(n²) algorithm beating an O(n log n) one, which is the part the notation deliberately hides.

big_o.pyPython 3
Output
How the code works
  1. return a[len(a) // 2], opsIndexing is O(1) because the address is computed, not searched for. The size of the list never enters into it — that is the whole meaning of constant time.
  2. mid = (lo + hi) // 2Halving the range each step means the op count rises by 1 when n doubles. In the table, n going from 10 to 1000 costs about seven more operations in total.
  3. for _ in a: for _ in a:Nested loops over the same collection: n² operations. At n = 1000 that is a million, and it is the single most common accidental complexity in real code.
  4. return len(a) + linearithmic(...) + ...Merge sort's recurrence made literal: linear work at each level, and log n levels. The number this returns is n log n up to a constant.
  5. insertion beats merge at n = 16Big-O describes growth as n gets large and deliberately discards the constant factor. At small n that constant is everything — which is why CPython's sort switches to insertion sort for short runs.
Change one thing
  • Add an O(2ⁿ) row using naive Fibonacci. Stop at n = 30; the table cannot reach 100.
  • Find the crossover: try n = 100, 200, 400 in the timing loop and see where merge overtakes insertion. Real libraries hard-code a number found exactly this way.
  • Feed the timing loop an already sorted list. Insertion sort's best case is O(n) and it wins at every size — complexity classes describe worst cases unless someone says otherwise.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: set input size n to its maximum (60). Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. Big-O describes:
  2. Which is O(1)?
  3. For n = 20, an O(n^2) algorithm may well beat an O(n log n) one. Why?





 Cheat sheet
Big-O Notation and Time Complexity
Compare O(1) through O(2^n) on the same input and see why constants vanish and growth rate is all that matters at scale.
ALGORITHMS · vizlearn.in/dsa/big_o_notation.html
More in Algorithms
AlgorithmsPython List LabAlgorithmsPython String LabAlgorithmsPython Dictionary LabAlgorithmsLinear Search
Further reading
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact