What is Big-O notation?

Big-O describes the upper-bound growth rate of an algorithm's time (or space) requirements relative to input size n. It ignores constant factors and focuses on how performance scales as n grows large.

Why does O(n log n) appear so often in sorting?

Comparison-based sorts (merge sort, heap sort, quicksort average case) need at least O(n log n) comparisons to sort n elements. This is a proven theoretical lower bound for comparison sorting.

When is O(n²) acceptable?

For small n (typically < 1 000), O(n²) algorithms like insertion sort are often faster in practice than O(n log n) algorithms due to lower constant factors and better cache behavior.

Why does O(n!) grow so much faster than O(2^n)?

Factorial growth multiplies by n at each step, while exponential growth multiplies by a fixed constant (2). For n=20, 2^n is about 1 million while 20! is about 2.4 quintillion — roughly 2.4 × 10^18.

Does Big-O measure the worst case only?

Big-O can express worst, average, or best case — but it is most commonly used for worst-case analysis. Omega notation (Ω) is used for best-case lower bounds, and Theta (Θ) for tight average-case bounds.

Big-O Complexity Explainer

Name: Big-O Complexity Explainer
Availability: InStock
Author: Nham Vu

Select an n value to see how many operations each complexity class requires, plus a Chart.js growth curve comparison for all major Big-O notations.

Big-O Complexity Reference

Big-O notation describes how an algorithm's resource usage scales with input size n. Adjust n below to see operation counts for every complexity class, and read the growth chart to understand how they diverge.

Input size n: (1 – 20; values above 20 are capped for factorial)

Notation	Name	Description	Example algorithms	Ops at n=10

Growth Curve Comparison

X axis: input size n (1–20). Y axis: approximate operation count (log scale).

O(1)

Constant

Execution time is fixed regardless of n. Ideal. Think array index lookup or hash table access.

O(log n)

Logarithmic

Input is halved each step. Binary search on a sorted array is the textbook example.

O(n)

Linear

Each additional element adds a fixed amount of work. A single pass through an array or linked list.

O(n log n)

Linearithmic

The optimal bound for comparison-based sorting. Merge sort, heap sort, and quicksort (average).

O(n²)

Quadratic

Nested loops over the input. Bubble sort, selection sort, and naive matrix multiplication.

O(2^n)

Exponential

Doubles with every additional element. Recursive subset enumeration, naive Fibonacci, traveling salesman (brute force).

O(n!)

Factorial

Permutation generation and brute-force TSP. Infeasible past n = 20 on any modern hardware.

O(n³)

Cubic

Triple nested loops. Naive matrix multiplication and Floyd–Warshall shortest path algorithm.

Summary

Select an n value to see how many operations each complexity class requires, plus a Chart.js growth curve comparison for all major Big-O notations.

How it works

For a user-supplied n, the tool evaluates each complexity formula (1, log2(n), n, n*log2(n), n^2, 2^n, n!) and renders the counts in a reference table. Chart.js plots growth curves across a range of n values so you can see visually how each class diverges.

Use cases

Compare algorithm candidates during a code review or interview prep.
Quickly look up what O(n log n) means relative to O(n²) for a given data size.
Teach Big-O to junior developers with a visual, interactive reference.
Estimate whether a brute-force approach is feasible before optimizing.
Use as a cheat-sheet during competitive programming or technical interviews.

Frequently Asked Questions

Last updated: 2026-06-11 · Reviewed by Nham Vu