Time Complexity Analysis Explained: Big O, Best/Worst Cases & Real Patterns

public class ComplexityGrowthDemo {

    public static void main(String[] args) {
        int[] inputSizes = {10, 100, 1_000, 10_000};

        System.out.printf("%-12s %-12s %-12s %-15s%n",
                "n", "O(n)", "O(n log n)", "O(n²)");
        System.out.println("-".repeat(55));

        for (int n : inputSizes) {
            long linearOps       = n;                            // grows in a straight line
            long nLogNOps        = (long)(n * (Math.log(n) / Math.log(2))); // grows slightly faster
            long quadraticOps   = (long) n * n;                // explodes as n grows

            System.out.printf("%-12d %-12d %-12d %-15d%n",
                    n, linearOps, nLogNOps, quadraticOps);
        }

        // The takeaway: at n=10,000, O(n²) is already 10,000x MORE work than O(n).
        // That gap keeps growing. This is why complexity class matters.
    }
}

import java.util.Arrays;

public class LinearSearchCaseAnalysis {

    /**
     * Standard linear search — returns index of target, or -1 if not found.
     * Best case:    O(1)   — target is at index 0
     * Worst case:   O(n)   — target is at last index or absent
     * Average case: O(n/2) => simplified to O(n) — target is somewhere in the middle
     */
    public static int linearSearch(int[] numbers, int target) {
        int comparisonsCount = 0;

        for (int index = 0; index < numbers.length; index++) {
            comparisonsCount++;                          // count every comparison we make
            if (numbers[index] == target) {
                System.out.printf("Found %d at index %d after %d comparison(s)%n",
                        target, index, comparisonsCount);
                return index;
            }
        }

        System.out.printf("%d not found after %d comparison(s)%n",
                target, comparisonsCount);
        return -1;
    }

    public static void main(String[] args) {
        int[] temperatures = {72, 65, 80, 91, 55, 88, 76, 60, 95, 70};

        System.out.println("Array: " + Arrays.toString(temperatures));
        System.out.println("Array size: " + temperatures.length + " elements");
        System.out.println();

        // Best case — target is the very first element: O(1)
        System.out.println("--- Best Case ---");
        linearSearch(temperatures, 72);

        // Average case — target is somewhere in the middle: O(n/2) → O(n)
        System.out.println("\n--- Average Case ---");
        linearSearch(temperatures, 88);

        // Worst case — target is last OR not present at all: O(n)
        System.out.println("\n--- Worst Case (last element) ---");
        linearSearch(temperatures, 70);

        System.out.println("\n--- Worst Case (not present) ---");
        linearSearch(temperatures, 99);
    }
}

import java.util.Arrays;

public class ComplexityPatternExamples {

    // O(1) — constant time, no matter how big the list is
    public static String getFirstCity(String[] cities) {
        return cities[0];  // direct index access, always one operation
    }

    // O(n) — single loop, one pass through all elements
    public static double calculateAverageTemperature(double[] readings) {
        double total = 0;
        for (double temp : readings) {   // visits each element exactly once
            total += temp;
        }
        return total / readings.length;
    }

    // O(n²) — nested loops, classic quadratic pattern
    // This checks every pair of products for duplicate names.
    public static boolean hasDuplicateProductName(String[] productNames) {
        for (int outerIndex = 0; outerIndex < productNames.length; outerIndex++) {
            for (int innerIndex = outerIndex + 1; innerIndex < productNames.length; innerIndex++) {
                // inner loop runs (n-1) + (n-2) + ... + 1 times total = n(n-1)/2 → O(n²)
                if (productNames[outerIndex].equals(productNames[innerIndex])) {
                    return true;
                }
            }
        }
        return false;
    }

    // O(log n) — binary search, problem halves every iteration
    public static int findPriceIndex(int[] sortedPrices, int targetPrice) {
        int left = 0;
        int right = sortedPrices.length - 1;

        int stepCount = 0;
        while (left <= right) {
            stepCount++;
            int midpoint = left + (right - left) / 2;   // avoids integer overflow vs (left+right)/2

            if (sortedPrices[midpoint] == targetPrice) {
                System.out.println("Binary search found in " + stepCount + " step(s)");
                return midpoint;
            } else if (sortedPrices[midpoint] < targetPrice) {
                left = midpoint + 1;   // discard left half
            } else {
                right = midpoint - 1;  // discard right half
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        // O(1) demo
        String[] capitals = {"Paris", "Tokyo", "Cairo", "Sydney"};
        System.out.println("First city: " + getFirstCity(capitals));

        // O(n) demo
        double[] weeklyTemps = {68.5, 72.1, 65.0, 80.3, 77.8, 69.2, 74.6};
        System.out.printf("Average temp: %.2f°F%n", calculateAverageTemperature(weeklyTemps));

        // O(n²) demo
        String[] inventory = {"Widget", "Gadget", "Doohickey", "Widget"};
        System.out.println("Has duplicate product name: " + hasDuplicateProductName(inventory));

        // O(log n) demo — array MUST be sorted for binary search
        int[] sortedPrices = {5, 12, 23, 37, 45, 58, 67, 82, 91, 99,
                              104, 118, 135, 147, 160}; // 15 elements
        int targetIndex = findPriceIndex(sortedPrices, 147);
        System.out.println("Price $147 found at index: " + targetIndex);
        // With 15 elements, log₂(15) ≈ 4 steps worst case — versus 15 for linear search
    }
}

import java.util.ArrayList;
import java.util.List;

public class SequentialVsNestedLoops {

    // O(n) — two SEQUENTIAL loops, not nested
    // Total work = n + n = 2n → simplifies to O(n)
    public static void printAllOrderSummaries(String[] orderIds, double[] orderTotals) {
        // First pass: print all order IDs — O(n)
        System.out.println("=== Order IDs ===");
        for (String orderId : orderIds) {
            System.out.println("  Order: " + orderId);
        }

        // Second pass: print all totals — O(n)
        // These are NOT nested, so the total is O(n) + O(n) = O(n)
        System.out.println("=== Order Totals ===");
        for (double total : orderTotals) {
            System.out.printf("  $%.2f%n", total);
        }
    }

    // O(n × m) — nested loops over DIFFERENT size variables
    // If m is bounded (e.g. always ≤ 5 tags), this is effectively O(n)
    // If m scales with input size, treat it as O(n × m)
    public static void printProductsWithTags(List<String> productNames,
                                              List<List<String>> productTags) {
        System.out.println("=== Products and Tags ===");
        for (int productIndex = 0; productIndex < productNames.size(); productIndex++) {
            // outer loop: n products
            System.out.print("  " + productNames.get(productIndex) + " → tags: ");

            List<String> tags = productTags.get(productIndex);
            for (String tag : tags) {    // inner loop: m tags per product
                System.out.print("[" + tag + "] ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // Demo sequential loops — O(n), NOT O(n²)
        String[] orderIds    = {"ORD-001", "ORD-002", "ORD-003"};
        double[] orderTotals = {49.99, 129.50, 18.75};
        printAllOrderSummaries(orderIds, orderTotals);

        System.out.println();

        // Demo nested loops over different variables — O(n × m)
        List<String> products = List.of("Laptop", "Headphones", "Keyboard");
        List<List<String>> tags = new ArrayList<>();
        tags.add(List.of("electronics", "computing"));         // 2 tags
        tags.add(List.of("audio", "wireless", "accessories")); // 3 tags
        tags.add(List.of("peripherals", "computing"));         // 2 tags
        // Here m (tags per product) is bounded and small — effectively O(n)
        printProductsWithTags(products, tags);
    }
}