Big O Notation Explained: Time & Space Complexity for Beginners

public class BigOConceptDemo {

    // O(1) — Constant Time
    // No matter how large the list is, grabbing the first element
    // always takes exactly one step. The size of the array is irrelevant.
    public static String getFirstItem(String[] shoppingList) {
        return shoppingList[0]; // Always one operation. Always.
    }

    // O(n) — Linear Time
    // We visit every item exactly once. Double the list = double the work.
    // This is like reading every page of a book to find one sentence.
    public static boolean containsItem(String[] shoppingList, String target) {
        for (String item : shoppingList) {       // Loop runs n times (n = list length)
            if (item.equals(target)) {           // One comparison per iteration
                return true;                     // Best case: first item. Worst case: last item.
            }
        }
        return false; // Item not found after checking everything
    }

    public static void main(String[] args) {
        String[] groceries = {"apples", "bread", "milk", "eggs", "butter"};

        // O(1) demo — instant regardless of list size
        String first = getFirstItem(groceries);
        System.out.println("First item (O(1)): " + first);

        // O(n) demo — scans the list until it finds the target
        boolean hasMilk = containsItem(groceries, "milk");   // Checks index 0, 1, 2 — stops
        boolean hasCake = containsItem(groceries, "cake");   // Checks ALL 5 items, finds nothing

        System.out.println("Has milk (O(n)): " + hasMilk);
        System.out.println("Has cake (O(n)): " + hasCake);

        // The key insight: even though 'milk' was found at index 2,
        // we still call this O(n) because Big O measures the WORST case.
        System.out.println("\nBig O measures worst case — always plan for the full scan.");
    }
}

public class ComplexityClassesDemo {

    // O(log n) — Binary Search
    // The array MUST be sorted. Each step eliminates HALF the remaining options.
    // Like a 'higher or lower' guessing game — always cut the range in half.
    public static int binarySearch(int[] sortedPrices, int targetPrice) {
        int leftBoundary = 0;
        int rightBoundary = sortedPrices.length - 1;

        while (leftBoundary <= rightBoundary) {
            int midpoint = leftBoundary + (rightBoundary - leftBoundary) / 2; // Avoids integer overflow

            if (sortedPrices[midpoint] == targetPrice) {
                return midpoint;           // Found it — return the index
            } else if (sortedPrices[midpoint] < targetPrice) {
                leftBoundary = midpoint + 1; // Target is in the RIGHT half, discard left
            } else {
                rightBoundary = midpoint - 1; // Target is in the LEFT half, discard right
            }
        }
        return -1; // Target not found in the array
    }

    // O(n²) — Find all duplicate pairs in a list
    // For every element, we check every OTHER element.
    // Two nested loops over the same data = quadratic time.
    public static void findDuplicatePairs(int[] scores) {
        System.out.println("Duplicate pairs found:");
        for (int outerIndex = 0; outerIndex < scores.length; outerIndex++) {          // n iterations
            for (int innerIndex = outerIndex + 1; innerIndex < scores.length; innerIndex++) { // up to n iterations
                if (scores[outerIndex] == scores[innerIndex]) {
                    System.out.println("  Score " + scores[outerIndex] +
                            " appears at index " + outerIndex + " and " + innerIndex);
                }
            }
        }
        // Total comparisons = n*(n-1)/2, which is O(n²)
    }

    public static void main(String[] args) {
        // Binary search demo — O(log n)
        int[] sortedPrices = {5, 12, 19, 27, 35, 44, 58, 73, 89, 100}; // Must be sorted!
        int targetPrice = 44;
        int foundAtIndex = binarySearch(sortedPrices, targetPrice);
        System.out.println("Binary Search O(log n):");
        System.out.println("  Price $" + targetPrice + " found at index: " + foundAtIndex);
        System.out.println("  Array has 10 elements — max steps needed: ~4 (log₂ of 10)");

        System.out.println();

        // Quadratic demo — O(n²)
        int[] studentScores = {85, 92, 78, 92, 85, 100};
        findDuplicatePairs(studentScores);
        System.out.println("  (6 elements = up to 15 comparisons with O(n²))");
    }
}

import java.util.HashMap;
import java.util.Map;

public class SpaceComplexityDemo {

    // APPROACH 1: O(n²) time, O(1) space
    // Check every pair of numbers to find two that sum to the target.
    // No extra memory used — but very slow for large inputs.
    public static int[] findPairBruteForce(int[] numbers, int targetSum) {
        for (int outerIndex = 0; outerIndex < numbers.length; outerIndex++) {
            for (int innerIndex = outerIndex + 1; innerIndex < numbers.length; innerIndex++) {
                if (numbers[outerIndex] + numbers[innerIndex] == targetSum) {
                    return new int[]{outerIndex, innerIndex}; // Found the pair
                }
            }
        }
        return new int[]{}; // No pair found
    }

    // APPROACH 2: O(n) time, O(n) space
    // Use a HashMap to remember what we've seen.
    // For each number, check if its 'complement' (targetSum - current) was seen before.
    // We trade memory (the HashMap) for speed (one single pass through the array).
    public static int[] findPairWithHashMap(int[] numbers, int targetSum) {
        // This HashMap is our 'extra memory' — it grows with the input = O(n) space
        Map<Integer, Integer> previouslySeen = new HashMap<>();

        for (int currentIndex = 0; currentIndex < numbers.length; currentIndex++) {
            int currentNumber = numbers[currentIndex];
            int neededComplement = targetSum - currentNumber; // What number do we need to pair with this one?

            if (previouslySeen.containsKey(neededComplement)) {
                // We've seen the complement before — we have our pair!
                return new int[]{previouslySeen.get(neededComplement), currentIndex};
            }

            // Haven't found the pair yet — store this number for future reference
            previouslySeen.put(currentNumber, currentIndex);
        }
        return new int[]{};
    }

    public static void main(String[] args) {
        int[] transactionAmounts = {15, 7, 42, 3, 28, 11};
        int targetSum = 39; // We want two transactions that total $39

        System.out.println("Finding two transactions that sum to $" + targetSum);
        System.out.println();

        // Brute force: slow but uses no extra memory
        int[] bruteResult = findPairBruteForce(transactionAmounts, targetSum);
        System.out.println("Brute Force O(n²) time / O(1) space:");
        System.out.println("  Indices: [" + bruteResult[0] + ", " + bruteResult[1] + "]");
        System.out.println("  Values: $" + transactionAmounts[bruteResult[0]] +
                " + $" + transactionAmounts[bruteResult[1]] + " = $" + targetSum);

        System.out.println();

        // HashMap: fast but uses extra memory
        int[] hashResult = findPairWithHashMap(transactionAmounts, targetSum);
        System.out.println("HashMap O(n) time / O(n) space:");
        System.out.println("  Indices: [" + hashResult[0] + ", " + hashResult[1] + "]");
        System.out.println("  Values: $" + transactionAmounts[hashResult[0]] +
                " + $" + transactionAmounts[hashResult[1]] + " = $" + targetSum);

        System.out.println();
        System.out.println("Same answer, very different resource usage.");
        System.out.println("With 1 million transactions, the HashMap approach wins by miles.");
    }
}