Log in
MODULE 18

Big O Calculator: Algorithm Complexity Analysis

Big-O Growth Comparison

Bubble Sort (step trace)

Binary Search (step trace)

What is Big O?

Algorithmic complexity measures how an algorithm's runtime grows as input size grows, using Big-O notation. It lets you predict whether an algorithm finishes in milliseconds or centuries before ever running it on real data.

How Does This Calculator Work?

Choose a sorting or searching algorithm, enter your array (and a target for search), and watch the algorithm execute step by step while the calculator tracks its Big-O complexity class.

Common Formulas & Rules

  • O(1) — constant time: runtime doesn't depend on input size (e.g. array index lookup).
  • O(log n) — logarithmic: runtime grows very slowly (e.g. binary search).
  • O(n) — linear: runtime grows proportionally with input size.
  • O(n log n): typical of efficient sorting algorithms like merge sort.
  • O(n²) — quadratic: typical of simple nested-loop algorithms like bubble sort.
  • O(2n) — exponential: typical of brute-force search over all subsets; becomes infeasible quickly.

Worked Example

Searching an unsorted list of a million items one by one takes up to a million comparisons (O(n)). Sorting it once with an O(n log n) algorithm costs about 20 million comparisons, but then every future search can use binary search at O(log n) — about 20 comparisons — a trade worth making if you'll search the same data many times.

Study guide: Algorithms & Complexity

Written for students learning this topic for the first time. Last updated October 2026.

Overview

Big-O notation describes how running time or memory grows with input size while ignoring constant factors. It lets you compare algorithms before running them and explains why some approaches stop working as data grows.

Key ideas explained

Big-O, Ω and Θ

f(n) = O(g(n)) means f(n) ≤ c·g(n) for some constant c and all large n. Ω gives a lower bound and Θ a tight bound. Drop constants and lower-order terms: 3n² + 10n + 7 = Θ(n²).

The growth hierarchy

From slow to fast: 1, log n, √n, n, n log n, n², n³, 2ⁿ, n!. At n = 20 these are about 4.3 for log₂ n, 400 for n², roughly 1.05 million for 2ⁿ, and about 2.4 × 10¹⁸ for n!.

Analysing loops and recursion

A single loop is O(n), nested loops O(n²), and a loop that halves its range O(log n). The recurrence T(n) = 2T(n/2) + n gives O(n log n), and T(n) = T(n/2) + 1 gives O(log n). Best, worst and average cases can differ.

Searching and sorting

Binary search needs sorted data and takes O(log n). Bubble sort is O(n²) in the worst case. Any comparison-based sort needs Ω(n log n) comparisons in the worst case, which merge sort achieves.

Worked examples

Tracing binary search

Problem. Find 23 in [3, 8, 12, 17, 23, 31, 45, 52] (indices 0–7).

  1. lo = 0, hi = 7, mid = 3: 17 < 23, so lo = 4.
  2. mid = 5: 31 > 23, so hi = 4.
  3. mid = 4: 23 found.

Answer. Found at index 4 after 3 comparisons. The worst case for 8 items is ⌊log₂ 8⌋ + 1 = 4.

Tracing bubble sort

Problem. Sort [5, 1, 4, 2].

  1. Pass 1: 5 bubbles to the end, giving [1, 4, 2, 5] after 3 swaps.
  2. Pass 2: 4 and 2 swap, giving [1, 2, 4, 5].
  3. Pass 3 makes no swaps, so the list is sorted.
  4. Total swaps = 4, equal to the number of inversions (5>1, 5>4, 5>2, 4>2).

Answer. [1, 2, 4, 5], using exactly one swap per inversion.

Enter these same values in the calculator above and compare each step with the working shown here.

Common mistakes to avoid

  • Treating Big-O as an exact running time, or as meaning “worst case” only. It is an upper bound that can describe any case.
  • Leaving constants or lower-order terms in the final answer.
  • Using binary search on unsorted data.
  • Assuming a smaller Big-O is always faster. For small inputs, constants can dominate.

Where this shows up in computer science

  • Choosing data structures: a hash map offers O(1) average lookups, a balanced tree O(log n).
  • Capacity planning: whether a feature that works on 1,000 rows will work on 10 million.
  • Cryptography relies on problems whose best-known attacks take exponential time.

Test yourself

Try each question before opening the answer.

What is the Big-O of 5n³ + 2n² + 100?

O(n³).

What is the most comparisons binary search needs on 1,000,000 sorted items?

⌊log₂ 1,000,000⌋ + 1 = 19 + 1 = 20.

Which grows faster, n² or 2ⁿ?

2ⁿ. They are equal at n = 4 (both 16), and 2ⁿ is larger for every n ≥ 5.

Frequently asked questions

What does O(n log n) mean in practice?

It describes runtime that grows faster than linear but much slower than quadratic — typical of efficient sorting algorithms like merge sort. Doubling the input roughly doubles the work plus a small log factor, not quadruples it.

Why does Big-O ignore constants?

Big-O describes growth trend at scale, not exact runtime. An algorithm that takes 100n steps and one that takes 2n steps are both O(n), because what matters long-term is that both scale linearly, not the specific multiplier.

What's the difference between best-case, average-case, and worst-case complexity?

Best-case is the fewest operations possible (e.g. searching finds the target immediately). Worst-case is the most operations possible. Average-case estimates typical performance across all possible inputs. Big-O usually refers to worst-case unless stated otherwise.