Complexity Analysis

Understand algorithmic time and space complexity using Big O notation, with intuitive summaries and examples.

What is Big O?

Big O describes how runtime or memory grows as input size n increases. It captures the dominant term, ignoring constants and lower-order terms.

Time vs Space

Time complexity measures steps executed; space complexity measures additional memory used beyond the input itself.

Best / Average / Worst

We often focus on worst-case for guarantees, average-case for typical behavior, and best-case for ideal scenarios.

Interactive growth visualizer

Compare O(1), O(log n), O(n), O(n log n), O(n²)

Input size n1,000

101001,00010,000

Scale mode

Show O(2^n)

Tip: Choose Log scale to compare functions that differ by orders of magnitude.

O(1)

O(log n)

O(n)

O(n log n)

O(n²)

O(1) — Constant

Runtime does not grow with input size. Single step operations.

Hash table lookup

Stack push/pop

Array access by index

O(log n) — Logarithmic

Problems reduced by a constant factor each step (divide-and-conquer search).

Binary search

Balanced BST operations

Heaps push/pop

O(n) — Linear

Work grows directly with input size. Single pass over data.

Linear search

One-pass aggregation

Copying an array

O(n log n) — Quasi-linear

Divide-and-conquer over all elements. Optimal comparison sorting boundary.

Merge sort

Quick sort (avg)

Heapsort

O(n²) — Quadratic

Nested loops over data. Pairwise comparisons across elements.

Bubble sort

Insertion/Selection sort (worst)

All pairs comparisons

O(2^n), O(n!) — Exponential/Factorial

Brute-force exploration of combinations or permutations.

Traveling Salesman (brute-force)

Subset enumeration

Backtracking worst-cases

How operations scale

n = 10

O(1)1

O(log n)4

O(n)10

O(n log n)34

O(n²)100

n = 100

O(1)1

O(log n)7

O(n)100

O(n log n)665

O(n²)10,000

n = 1,000

O(1)1

O(log n)10

O(n)1,000

O(n log n)9,966

O(n²)1,000,000

n = 10,000

O(1)1

O(log n)14

O(n)10,000

O(n log n)132,878

O(n²)100,000,000

These counts are indicative only (base-2 log shown). Real constants and lower-order terms are omitted in Big O.

Practical guidance

Prefer O(n log n) or better for large-scale sorting/searching tasks.

Amortized and average-case often matter in practice; know your data.

Constant factors, cache locality, and implementation details impact real-world speed.

Beware quadratic algorithms on large inputs unless n is small or bounded.

Space complexity matters on memory-constrained systems; prefer in-place where feasible.

Use data-structure invariants (e.g., heap, BST balance) to achieve better bounds.

CS Visualize

Complexity Analysis

What is Big O?

Time vs Space

Best / Average / Worst

Interactive growth visualizer

O(1) — Constant

O(log n) — Logarithmic

O(n) — Linear

O(n log n) — Quasi-linear

O(n²) — Quadratic

O(2^n), O(n!) — Exponential/Factorial

How operations scale

Practical guidance