Key facts

  • Paul Bachmann introduced Big-O notation in 1894, and Edmund Landau popularised it in 1909;
  • John von Neumann described merge sort in 1945; it is a stable divide-and-conquer sorting algorithm with O(n log n) time in best, average and worst cas...
  • E. W. Dijkstra published the single-source shortest path algorithm in 1959; it works for graphs with non-negative edge weights.
  • C. A. R. Hoare published quicksort in 1961; its average time is O(n log n), but poor pivot choice can degrade it to O(n^2).
  • G. M. Adelson-Velsky and E. M. Landis introduced the AVL tree in 1962; it was the first widely cited self-balancing binary search tree.

Key Points at a Glance

  1. 1

    Paul Bachmann introduced Big-O notation in 1894, and Edmund Landau popularised it in 1909; it expresses upper-bound growth of time or space as input size increases.

  2. 2

    John von Neumann described merge sort in 1945; it is a stable divide-and-conquer sorting algorithm with O(n log n) time in best, average and worst cases.

  3. 3

    E. W. Dijkstra published the single-source shortest path algorithm in 1959; it works for graphs with non-negative edge weights.

  4. 4

    C. A. R. Hoare published quicksort in 1961; its average time is O(n log n), but poor pivot choice can degrade it to O(n^2).

  5. 5

    G. M. Adelson-Velsky and E. M. Landis introduced the AVL tree in 1962; it was the first widely cited self-balancing binary search tree.

  6. 6

    Robert W. Floyd and Stephen Warshall published dynamic programming graph algorithms in 1962; the Floyd-Warshall algorithm solves all-pairs shortest paths.

  7. 7

    J. W. J. Williams introduced heapsort in 1964; the binary heap supports efficient priority-queue operations and in-place O(n log n) sorting.

SENIOR COMPUTER INSTRUCTOR study hubView study packs

Complexity, growth rates and asymptotic notation

Algorithm analysis compares procedures by how resource use grows with input size, not by one machine's clock speed. Time complexity counts dominant operations; space complexity counts extra memory required beyond the input. In objective papers, the common order is O(1), O(log n), O(n), O(n log n), O(n^2), O(n^3), O(2^n) and O(n!). Constant factors and lower-order terms are ignored for asymptotic comparison, so 5n + 20 and 100n are both O(n), while n^2 + n is O(n^2).

Big-O gives an upper bound, Omega gives a lower bound, and Theta gives a tight bound when upper and lower growth match. Worst-case analysis is normally safest for examination answers, but average-case and best-case are also asked for sorting and searching. Amortised analysis spreads a sequence cost across operations, such as dynamic-array resizing where occasional O(n) copying still gives O(1) amortised insertion at the end.

Exam focus: always identify the input parameter, the dominant loop or recurrence, and whether memory is auxiliary space or total space.

Open the complete note

This public page shows the first available section. The study pack opens the complete topic with all revision material.

7 more sections in the complete note

Open study pack