Algorithmic Thinking Advanced

Divide and conquer is a strategy that splits a problem into two or more smaller versions of the same problem, solves each recursively, and combines the results. It is the idea behind merge sort, binary search, and many fast algorithms.

Divide and conquer — merge sort idea:
  To sort [8, 3, 5, 1, 9, 2, 7, 4]:
    DIVIDE:  [8, 3, 5, 1]  and  [9, 2, 7, 4]
    RECURSE: sort each half independently
    CONQUER: merge the two sorted halves into one sorted list

The power of divide and conquer comes from the fact that halving the problem size repeatedly leads to far fewer total steps than processing everything at once. This is why merge sort is much faster than bubble sort for large inputs.

Different algorithm strategies make different trade-offs between correctness, speed, and simplicity.

• Brute force: try every possible solution and pick the best. Always correct, but often too slow for large inputs.
• Greedy: at each step, choose the locally best option without reconsidering. Fast and often correct, but not always optimal.
• Heuristic: a rule of thumb that finds a good-enough solution quickly, without guaranteeing the best answer. Used when exact solutions are impractical.

Example — coin change (making 30p from coins of 20p, 10p, 5p, 1p):
  Greedy: pick largest coin that fits → 20p + 10p = 30p  ✓ (optimal here)
  Brute force: try all combinations → also finds 30p but much slower

Choosing the right strategy depends on the problem constraints: size of input, acceptable running time, and whether an approximate answer is good enough.

A recursive algorithm solves a problem by calling itself on a smaller sub-problem. Every recursive algorithm needs two parts:

• Base case: the simplest input that can be answered directly without further recursion.
• Recursive case: reduce the problem to a smaller version and call the algorithm again.

Factorial (n! = n × (n-1) × … × 1):
  PROCEDURE factorial(n):
      IF n = 0 THEN RETURN 1        ← base case
      RETURN n × factorial(n - 1)   ← recursive case

  factorial(4) = 4 × factorial(3)
               = 4 × 3 × factorial(2)
               = 4 × 3 × 2 × factorial(1)
               = 4 × 3 × 2 × 1 × factorial(0)
               = 4 × 3 × 2 × 1 × 1 = 24

Without a base case, or if the recursive case never reaches it, the algorithm recurses indefinitely — a stack overflow.

Big-O notation describes how an algorithm's running time (or memory use) grows as the input size n increases. It focuses on the dominant pattern of growth, ignoring constants and smaller terms.

• O(1) — constant: same time regardless of n. Example: reading the first item of a list.
• O(log n) — logarithmic: doubles input → one extra step. Example: binary search.
• O(n) — linear: doubles input → twice the steps. Example: linear search.
• O(n²) — quadratic: doubles input → four times the steps. Example: comparing every pair in a list.

Growth comparison for n = 1 000 000:
  O(1)     →        1 step
  O(log n) →       20 steps   (log₂ of 1 000 000 ≈ 20)
  O(n)     →  1 000 000 steps
  O(n²)   → 10¹² steps        (too slow for most hardware)

Big-O is a tool for comparing algorithms at scale — small inputs rarely matter, but for large n the class of growth dominates everything else.

The state of an algorithm at any point is the collection of all current variable values. Reasoning about state — what is true at each step — is essential for proving correctness.

A loop invariant is a condition that is true before the loop starts, remains true after every iteration, and at the end implies the algorithm is correct.

Example — invariant for finding the minimum of a list:
  SET min TO list[0]
  Invariant: "min is the smallest value seen so far"
  FOR each remaining item x IN list:
      IF x < min THEN SET min TO x
      (invariant still holds after each step)
  After loop: min is the smallest value in the whole list ✓

Identifying invariants transforms informal reasoning about "does this loop work?" into a rigorous argument. They are widely used in algorithm proofs and formal verification.

Turning a real-world problem into an algorithm requires several steps: identifying inputs and outputs, choosing appropriate data representations, and selecting a strategy. This modelling step often separates a clear solution from an unworkable one.

Example — find the shortest path in a city road network:
  INPUTS:   map of roads and distances, start location, end location
  OUTPUT:   ordered list of roads to travel, total distance
  MODEL:    represent the map as a graph (nodes = intersections,
            edges = roads with distances)
  STRATEGY: apply a shortest-path algorithm (e.g., greedy approach
            that always explores the nearest unvisited node)

Good modelling involves choosing an abstraction that captures the essential structure of the problem without unnecessary complexity. The wrong model can make a solvable problem appear impossible.

In practice, algorithmic choices involve trade-offs. It is rarely possible to optimise everything at once — improving one dimension often worsens another.

• Time vs space: storing pre-computed results (caching) uses more memory but reduces computation time.
• Correctness vs speed: a heuristic runs faster but may not always find the best answer.
• Simplicity vs efficiency: a simple O(n²) sort may be preferable for tiny inputs where the overhead of a complex O(n log n) sort is not justified.

Trade-off example — searching repeated times:
  Option A: leave list unsorted, use linear search each time → O(n) per search
  Option B: sort once (O(n log n)), then binary search each time → O(log n) per search
  Verdict: if many searches are needed, the upfront sort cost pays off quickly

Good algorithm designers understand that context determines the right choice: input size, frequency of operations, available memory, and acceptable accuracy all influence the decision.

An algorithm must first be correct — it must produce the right answer for all valid inputs. Only once correctness is established does it make sense to focus on efficiency.

Correctness can be verified by:

• Tracing through examples (including edge cases).
• Proving a loop invariant holds throughout.
• Showing the base case and recursive case are both correct (for recursive algorithms).

Efficiency is then evaluated using Big-O analysis and measured by profiling on real data. The goal is the simplest algorithm that is correct and fast enough for the required input size — over-engineering for efficiency at the expense of clarity is itself a mistake.

Design order:
  1. Make it correct (pass all cases).
  2. Make it clear (readable, maintainable).
  3. Make it fast (only if needed for scale).