Algorithms & Data Structures in Java

What you'll learn

Algorithms (step-by-step procedures) and data structures (ways to organise data) are the bedrock of computer science — and the heart of coding interviews. This module gives you the essential mental models and the ability to reason about efficiency.

By the end you'll be able to:

• Analyse efficiency with Big-O notation
• Choose the right data structure for a task
• Implement and compare searching and sorting algorithms
• Apply core techniques: recursion, divide & conquer, greedy, dynamic programming

Big-O notation

Big-O describes how an algorithm's time (or memory) grows as the input grows. It ignores constants and focuses on the shape of growth — because at scale, that shape is what matters. An O(n²) algorithm that's fine for 100 items may be unusable for a million:

Core data structures

You met the collection classes in Module 14 — here's how they perform. Choosing the right structure is often the single biggest performance decision you'll make:

Searching

Linear search checks every element — O(n), works on any data. Binary search is dramatically faster — O(log n) — but requires sorted data. It repeatedly halves the search space, so finding an item among a billion takes only ~30 steps:

static int binarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (arr[mid] == target) return mid;   // found
        if (arr[mid] < target)  lo = mid + 1;  // search right half
        else                    hi = mid - 1;  // search left half
    }
    return -1;                                  // not found
}

public static void main(String[] args) {
    int[] sorted = {1, 3, 5, 7, 9, 11};        // MUST be sorted
    System.out.println(binarySearch(sorted, 7));  // -> 3
    System.out.println(binarySearch(sorted, 4));  // -> -1
}

Sorting

Sorting is a classic study in trade-offs. Simple sorts like bubble and insertion sort are O(n²) — easy to write, slow at scale. Efficient sorts like merge sort and quicksort are O(n log n) and are what real libraries use.

Key techniques

A handful of problem-solving strategies unlock most algorithmic problems:

• Recursion — solve a problem via smaller versions of itself (Module 6)
• Divide & conquer — split, solve the parts, combine (merge sort, binary search)
• Greedy — take the locally best choice at each step (works for some problems)
• Dynamic programming — cache overlapping subproblems so you never recompute them

Naive recursive Fibonacci is O(2ⁿ) because it recomputes the same values endlessly. Adding a cache — memoization, the essence of dynamic programming — makes it O(n):

static long[] memo = new long[50];

static long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];          // reuse cached result
    return memo[n] = fib(n - 1) + fib(n - 2);  // compute once, store
}

public static void main(String[] args) {
    System.out.println(fib(40));   // instant, thanks to memoization
}

Recap & quick check

Excellent — you can now reason about efficiency and pick the right tools. Next up: Module 36 — Security Fundamentals.