Skip to content
notes.vinhnq.com

Search

Data Structures & AlgorithmsJunior17 min read

Basic algorithms: Big-O and the three O(n²) sorts

Review 11 cards
On this page

Basic algorithms series: 1. Big-O and O(n²) sorts · 2. Recursion and binary search · 3. Merge sort and quicksort

Two correct pieces of code can differ from milliseconds to an hour on a million records. After this post you can read Big-O off code, estimate whether code will finish in time, and explain the three basic sorts: insertion, bubble and selection. There’s nothing to read first; part 2 covers recursion, binary search and a few classic problems, part 3 covers merge sort, quicksort and how Java really sorts, and the data structures live in Data Structures.

At a glance:

flowchart TD
  A["Big-O: growth with n"] --> B["Sequential: add"]
  A --> C["Nested: multiply"]
  A --> D["Halving: O(log n)"]
  E{"Which O(n²) sort?"} -->|"Default"| F["Insertion: stable, near O(n)"]
  E -->|"Writes very costly"| G["Selection: at most n-1 swaps"]
  E -->|"Almost never"| H["Bubble"]

1. Algorithm complexity

Key idea: complexity measures how cost grows as the input size n grows, by counting steps rather than timing seconds. Big-O is the shorthand for that growth.

1.1. What it is

We don’t measure in seconds because the result depends on the machine, the JIT and the data. There are two kinds:

  • Time complexity: how many basic operations are needed, counted through loop iterations, comparisons, assignments and so on.
  • Space complexity: how much extra memory the algorithm allocates.

One version of the slides says space is counted “excluding input and output”. The precise name for that is auxiliary space. When asked about “space complexity”, clarify, or say out loud that you mean auxiliary space. For instance, merge sort needs O(n) auxiliary space, insertion sort only O(1).

1.2. Big-O notation

Key idea: O(f(n)) means that for large enough n, the cost never exceeds c · f(n) for some constant c. Two rules: drop constants, keep only the fastest-growing term.

  • Drop constants: 3n + 5 becomes O(n); n²/2 becomes O(n²).
  • Keep the biggest term: n² + 100n + 7 becomes O(n²).
Ω, Θ, best/average/worst case and amortized

Two related symbols come up in interviews: Ω (Omega) is a lower bound, Θ (Theta) is a tight bound (both upper and lower). In everyday speech people say “Big-O” when they really mean Θ of the worst case.

  • Best / average / worst case: the cost of one run on different kinds of input. Insertion sort is O(n) at best (already sorted) and O(n²) at worst (reverse sorted).
  • Amortized cost: the average over a sequence of operations. ArrayList.add is O(1) amortized even though it occasionally has to resize.

1.3. Working out Big-O

Key idea: each assignment is O(1); blocks in sequence add, nested blocks multiply, then drop the constants.

Code shape Cost Result
1. One loop of n T(n) = c·n O(n)
2. Two nested loops of n each c·n·n O(n²)
3. Inner loop runs i times, i = 1..n c·n(n+1)/2 O(n²)
4. Inner loop always runs 20 times 20·c·n O(n)
5. A 10-step loop, then a 20·n loop 10c + 20cn O(n)
6. Throw away half each step n / 2^k = 1 so k = log₂ n O(log n)

O(1) is called constant time: the running time doesn’t depend on the input size. Worth memorizing: 1 + 2 + ... + n = n(n+1)/2.

The base of the logarithm doesn’t matter in Big-O because log₂ n = log₁₀ n / log₁₀ 2, which differs only by a constant.

Code for the 6 examples and the slides’ two O(log n) illustrations

The code is mine, written to illustrate the same cases as the slides.

Example 1: a single loop. Each assignment takes some constant time c, i.e. O(1). Run it n times and you get O(n).

int k = 0;
for (int i = 0; i < n; i++) {
    k = k + 5;          // O(1)
}

Example 2: two nested loops of n each.

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        k = k + i + j;

Example 3: an inner loop that depends on the outer one. The total is c(1 + 2 + ... + n) = (c/2)n² + (c/2)n, so O(n²).

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
        k = k + i + j;

Example 4: an inner loop with a fixed count. The 20 is a constant and gets dropped.

for (int i = 0; i < n; i++)
    for (int j = 0; j < 20; j++)
        k = k + i + j;

Example 5: two loops one after another.

for (int j = 0; j < 10; j++) k = k + 4;
for (int i = 0; i < n; i++)
    for (int j = 0; j < 20; j++)
        k = k + i + j;

Example 6: O(log n). The two copies of the slides use different examples:

  • Copy 1: binary search. Each step throws away half the array, so after k steps n / 2^k elements remain; it stops at 1, i.e. k = log₂ n.
  • Copy 2: computing aⁿ with n = 2^k by repeated squaring: a² = a·a, a⁴ = a²·a², … That takes k = log₂ n multiplications instead of n - 1.
// a^n where n = 2^k: square k times
static long powerOfTwoExponent(long a, int k) {
    long result = a;
    for (int i = 0; i < k; i++) result = result * result;
    return result;   // powerOfTwoExponent(3, 3) = 3^8 = 6561
}

Exercise 1 in part 2, on recursion shows how to compute xⁿ for any n.

1.4. Comparing growth rates

Key idea: O(n log n) is usually fine at n = 10⁶; O(n²) is only fine up to about n = 10⁴; exponential and factorial only survive tiny n.

Big-O Name n = 10³ n = 10⁶ Example
O(1) constant 1 1 a[i], average HashMap.get
O(log n) logarithmic ~10 ~20 binary search, TreeMap operations
O(n) linear 10³ 10⁶ scanning an array, linear search
O(n log n) linearithmic ~10⁴ ~2·10⁷ merge sort, Arrays.sort
O(n²) quadratic 10⁶ 10¹² bubble/insertion/selection sort
O(n³) cubic 10⁹ (seconds) 10¹⁸, infeasible three nested loops, naive n×n matrix multiplication, Floyd–Warshall
O(2ⁿ) exponential infeasible infeasible naive recursive Fibonacci, all subsets
O(n!) factorial infeasible infeasible all permutations

The doubling test. Ask: if the input doubles, how much more does it cost?

Big-O When n doubles, the cost… Example, n from 1,000 to 2,000
O(1) stays the same 1 → 1
O(log n) grows by one step ~10 → ~11
O(n) doubles 1,000 → 2,000
O(n log n) a bit more than doubles ~10,000 → ~22,000
O(n²) quadruples 10⁶ → 4·10⁶
O(2ⁿ) gets squared (2²ⁿ = (2ⁿ)²) hopeless from the start

It works on real measurements too: run with n and 2n, and if the time goes up about 4x, there’s almost certainly an O(n²) nested loop somewhere.

Notes on the slide chart and the O(n³), O(2ⁿ), O(n!) group
  • The slide’s chart also draws an O(n³) curve, mislabelled “O(x³)” and “O(x²)” (with x instead of n).
  • At n = 10³, O(n³) still finishes in seconds, but push n to 10⁴ and it becomes 10¹², which takes hours.
  • O(2ⁿ) usually shows up in backtracking without pruning; O(n!) in generating every permutation. Both only survive tiny inputs: around 20–25 for 2ⁿ, around 10–12 for n!.

2. Basic sorting algorithms

Key idea: all three are O(n²); they differ in best case, stability and number of swaps. You learn them for the problem-solving strategies and to understand the library’s sort, not to replace Arrays.sort.

Two terms first:

  • Stable: elements with equal keys keep their original relative order.
  • In-place: needs only O(1) extra memory.
Why learn sorting when Arrays.sort exists

The slides give three reasons, and I agree with them:

  1. Sorting algorithms show off many problem-solving strategies (incremental building, divide and conquer, picking the best candidate) that carry over to other problems.
  2. They’re great practice for basic programming skills: loops, conditionals, arrays, methods.
  3. They’re the clearest way to compare algorithm performance.

A fourth reason for backend engineers: understanding stability and in-place sorting tells you when the library’s sort will do what you expect (see part 3).

2.1. Insertion sort

Key idea: keep a prefix of the array always sorted; at each step take the next element and insert it into the right spot in that prefix, the way you sort a hand of cards as you pick them up.

static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int current = a[i];
        int k = i - 1;
        while (k >= 0 && a[k] > current) {   // > (not >=) keeps it stable
            a[k + 1] = a[k];
            k--;
        }
        a[k + 1] = current;
    }
}
  • Complexity: worst/average O(n²), best O(n) when the array is nearly sorted (the while barely runs).
  • Stable, in-place and online (it can sort data as it arrives).
  • Very fast on small arrays because of its low overhead. That’s why the JDK’s sorting algorithms switch to insertion sort for runs of a few dozen elements.
Insertion sort steps and a hand trace of [5, 2, 4, 1]
  1. For i from 1 to n-1, set current = a[i]. At this point a[0..i-1] is sorted.
  2. Walk k back from i-1 to 0: while a[k] > current, shift a[k] one slot right (a[k+1] = a[k]).
  3. When you hit a[k] <= current (or run off the front), stop and place a[k+1] = current.
i current Array after the step
1 2 [2, 5, 4, 1]
2 4 [2, 4, 5, 1]
3 1 [1, 2, 4, 5]

2.2. Bubble sort

Key idea: compare adjacent pairs and swap them if the left one is bigger; after each pass, the largest remaining element has “bubbled up” to the end of the unsorted part.

Fixing the slide’s indexing for bubble sort

The slides describe it as “at iteration k = 0..n, find the n-th largest and push it to position n - i”, which mixes up the indices. Precisely: after pass k (counting from 0), the (k+1)-th largest element sits at its final position n-1-k, so the next pass only needs to go up to n-2-k.

static void bubbleSort(int[] a) {
    for (int end = a.length - 1; end > 0; end--) {
        boolean swapped = false;
        for (int j = 0; j < end; j++) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp;
                swapped = true;
            }
        }
        if (!swapped) return;   // a pass with no swaps -> already sorted
    }
}
  • Complexity: O(n²); thanks to the swapped flag, O(n) at best.
  • Stable, in-place.
  • Almost never used in practice: it does the most swaps of the three.

2.3. Selection sort

Key idea: find the smallest element and put it first, find the smallest of what’s left and put it second, and so on.

static void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < a.length; j++)
            if (a[j] < a[min]) min = j;
        if (min != i) {
            int tmp = a[i]; a[i] = a[min]; a[min] = tmp;
        }
    }
}
  • Complexity: always O(n²) comparisons, even on sorted input.
  • In-place but not stable: a long-distance swap can jump an element over an equal one. Take [2a, 2b, 1]: swapping 2a with 1 gives [1, 2b, 2a].
  • Its one strength: at most n - 1 swaps, useful when writes are very expensive.

2.4. The three side by side

Key idea: if you must pick, pick insertion sort; selection sort only when writes are very expensive; bubble sort almost never.

Interactive visualisations

Key idea: stepping through an animation with a few arrays of your own is the fastest way to remember the three sorts.

Animations from Y. Daniel Liang’s textbook:

Exercises

Exercise 1: Print largest, smallest, second largest, second smallest…

Task (paraphrased): given an array of n distinct integers (1 ≤ n ≤ 1000), print them in the order largest, smallest, second largest, second smallest, and so on. For example, {9, 7, 12, 8, 6, 5} gives 12 5 9 6 8 7.

Solution to Exercise 1: sort, then two pointers

Sort ascending, then use two pointers: hi from the end and lo from the start, taking turns.

static int[] maxMinOrder(int[] input) {
    int[] a = input.clone();          // don't mutate the caller's array
    Arrays.sort(a);
    int[] out = new int[a.length];
    int lo = 0, hi = a.length - 1, k = 0;
    while (lo <= hi) {
        out[k++] = a[hi--];
        if (lo <= hi) out[k++] = a[lo++];   // odd n: take the middle element only once
    }
    return out;
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) a[i] = in.nextInt();
    StringJoiner sj = new StringJoiner(" ");
    for (int v : maxMinOrder(a)) sj.add(String.valueOf(v));
    System.out.println(sj);
}

O(n log n) for the sort; the two-pointer pass is O(n). With n ≤ 1000, a hand-written insertion sort would also be fast enough (about 10⁶ steps), which makes it a reasonable place to use section 2.

Remember

  • Can you read the Big-O of code with nested loops, sequential loops and halving loops?
  • Can you say how running time changes when n doubles, and use 10⁸ operations/second to estimate?
  • Can you tell worst case, average case and amortized apart (e.g. ArrayList.add)?
  • Can you explain why selection sort isn’t stable and why insertion sort is still in the JDK?
  • Can you show the a[i]-instead-of-a[min] bug with the counter-example [3, 1, 2]?

Interview questions

Junior

What is Big-O, and why do we drop constants?

Big-O is an upper bound on how cost grows as n gets large; constants are dropped because for large enough n, the shape of the function is what dominates.

Constants depend on the machine, the language and the compiler, while n versus n² is a fundamental difference. For small n, though, constants still matter in practice.

What does a stable sort mean?

Elements with equal keys keep the relative order they had before sorting.

Insertion and bubble sort are stable; selection sort isn’t.

If the input doubles, how does the running time of O(1), O(log n), O(n) and O(n²) change?

O(1) stays the same, O(log n) adds one step, O(n) doubles, O(n²) quadruples.

O(log n) adds only one step because log₂(2n) = log₂ n + 1. O(n log n) slightly more than doubles; O(2ⁿ) gets squared. It’s also a quick benchmark check: measure at n and 2n, and the ratio tells you the growth rate.

Mid

A selection sort uses if (a[j] < a[i]) min = j;. What’s wrong? Give a counter-example.

It must compare against a[min] (the smallest value found so far), not a[i]; the counter-example [3, 1, 2] ends up as [2, 1, 3].

Against a[i], min is just the last position that’s smaller than a[i]. For [3, 1, 2], the first pass ends with min = 2 and the swap gives [2, 1, 3]; later passes change nothing. The lesson: in a “pick the best element” algorithm, the running best is what you compare against; and always test on small arrays with several competing elements, checking against Arrays.sort.

Why do standard libraries still use insertion sort if it’s O(n²)?

Because its constant factors are tiny on small arrays, and on nearly sorted data it’s close to O(n).

No recursion, sequential access, very little overhead. That’s why hybrid algorithms like TimSort and the JDK’s dual-pivot quicksort fall back to insertion sort for small ranges (a few dozen elements).

What’s the difference between best, average and worst case, and amortized cost?

Best/average/worst case describe one run on different kinds of input; amortized is the average over a sequence of operations, with no probability involved.

  • Insertion sort: O(n) at best on sorted input, O(n²) at worst on reversed input, O(n²) on average.
  • ArrayList.add is occasionally O(n) when it resizes, but n adds cost O(n) in total, so each is O(1) amortized.
  • Average case needs an assumption about the input distribution; amortized doesn’t.
Why isn’t selection sort stable, and when is it still worth using?

Because its long-distance swap can jump an element over another with the same key; it’s only worth using when writes are very expensive.

For [2a, 2b, 1], swapping 2a with 1 gives [1, 2b, 2a], so the two 2s are reversed. Its one strength is at most n - 1 swaps, which helps when writes are expensive (flash memory, for instance); otherwise insertion sort is better.

Senior

When can an O(n log n) algorithm be slower than an O(n²) one in practice?

When n is small: constants and hardware effects dominate, because Big-O only describes the trend as n → ∞.

Insertion sort on 20 elements beats merge sort because it doesn’t allocate, doesn’t recurse and accesses memory sequentially. That’s why hybrid algorithms exist, and why you measure with a benchmark (JMH) instead of reasoning alone.

Useful phrases for interviews

  • “Let me start with the brute force, which is O(n²), and then see where we’re doing repeated work.”
  • “The bottleneck here is the sort; everything after it is linear.”
  • “Asymptotically they’re the same, but this one has much better constant factors.”
  • “A quick back-of-the-envelope check: 10⁶ squared is 10¹² operations, which is way too slow.”
  • “If the input doubles, a quadratic algorithm takes four times as long, so this won’t scale.”
  • “Insertion sort is my pick among the three: it’s stable, in-place, and nearly linear on almost-sorted data.”
  • “Amortized cost is averaged over a sequence of operations, not over random inputs.”
  • “Selection sort isn’t stable because the long-distance swap can jump an element over an equal one.”

Notes based on the Fundamentals of Backend course (Ronin Engineer) and the Hỏi Dân IT Java Core material, rewritten in my own words.