Time Complexity Analysis — Nested Loop Killed 10M Products

package io.thecodeforge.complexity;

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.
    }
}

package io.thecodeforge.complexity;

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) {\n        int comparisonsCount = 0;\n\n        for (int index = 0; index < numbers.length; index++) {\n            comparisonsCount++;                          // count every comparison we make\n            if (numbers[index] == target) {\n                System.out.printf(\"Found %d at index %d after %d comparison(s)%n\",\n                        target, index, comparisonsCount);\n                return index;\n            }\n        }\n\n        System.out.printf(\"%d not found after %d comparison(s)%n\",\n                target, comparisonsCount);\n        return -1;\n    }\n\n    public static void main(String[] args) {\n        int[] temperatures = {72, 65, 80, 91, 55, 88, 76, 60, 95, 70};\n\n        System.out.println(\"Array: \" + Arrays.toString(temperatures));\n        System.out.println(\"Array size: \" + temperatures.length + \" elements\");\n        System.out.println();\n\n        // Best case — target is the very first element: O(1)\n        System.out.println(\"--- Best Case ---\");\n        linearSearch(temperatures, 72);\n\n        // Average case — target is somewhere in the middle: O(n/2) → O(n)\n        System.out.println(\"\\n--- Average Case ---\");\n        linearSearch(temperatures, 88);\n\n        // Worst case — target is last OR not present at all: O(n)\n        System.out.println(\"\\n--- Worst Case (last element) ---\");\n        linearSearch(temperatures, 70);\n\n        System.out.println(\"\\n--- Worst Case (not present) ---\");\n        linearSearch(temperatures, 99);\n    }\n}",
        "output": "Array: [72, 65, 80, 91, 55, 88, 76, 60, 95, 70]\nArray size: 10 elements\n\n--- Best Case ---\nFound 72 at index 0 after 1 comparison(s)\n\n--- Average Case ---\nFound 88 at index 5 after 6 comparison(s)\n\n--- Worst Case (last element) ---\nFound 70 at index 9 after 10 comparison(s)\n\n--- Worst Case (not present) ---\n99 not found after 10 comparison(s)"
      }

package io.thecodeforge.complexity;

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
    }
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>

// O(1) — constant
int getFirst(const std::vector<int>& vec) {
    return vec[0];
}

// O(n) — linear
int sum(const std::vector<int>& vec) {
    int total = 0;
    for (int val : vec) {
        total += val;
    }
    return total;
}

// O(n²) — nested loop (duplicate check)
bool hasDuplicates(const std::vector<int>& vec) {
    for (size_t i = 0; i < vec.size(); ++i) {
        for (size_t j = i + 1; j < vec.size(); ++j) {
            if (vec[i] == vec[j]) return true;
        }
    }
    return false;
}

// O(log n) — binary search (assuming sorted input)
bool binarySearch(const std::vector<int>& sortedVec, int target) {\n    return std::binary_search(sortedVec.begin(), sortedVec.end(), target);\n}

// O(n log n) — sorting
void sortVector(std::vector<int>& vec) {
    std::sort(vec.begin(), vec.end());
}

int main() {
    std::vector<int> data = {5, 3, 8, 1, 9, 2};

    std::cout << "First element (O(1)): " << getFirst(data) << '\n';
    std::cout << "Sum (O(n)): " << sum(data) << '\n';
    std::cout << "Has duplicates (O(n²)): " << hasDuplicates(data) << '\n';

    std::sort(data.begin(), data.end());  // sort before binary search
    std::cout << "Binary search for 3 (O(log n)): " << binarySearch(data, 3) << '\n';

    return 0;
}

package io.thecodeforge.complexity;

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) {\n        System.out.println(\"=== Products and Tags ===\");\n        for (int productIndex = 0; productIndex < productNames.size(); productIndex++) {\n            // outer loop: n products\n            System.out.print(\"  \" + productNames.get(productIndex) + \" → tags: \");\n\n            List<String> tags = productTags.get(productIndex);\n            for (String tag : tags) {    // inner loop: m tags per product\n                System.out.print(\"[\" + tag + \"] \");\n            }\n            System.out.println();\n        }\n    }\n\n    public static void main(String[] args) {\n        // Demo sequential loops — O(n), NOT O(n²)\n        String[] orderIds    = {\"ORD-001\", \"ORD-002\", \"ORD-003\"};\n        double[] orderTotals = {49.99, 129.50, 18.75};\n        printAllOrderSummaries(orderIds, orderTotals);\n\n        System.out.println();\n\n        // Demo nested loops over different variables — O(n × m)\n        List<String> products = List.of(\"Laptop\", \"Headphones\", \"Keyboard\");\n        List<List<String>> tags = new ArrayList<>();\n        tags.add(List.of(\"electronics\", \"computing\"));         // 2 tags\n        tags.add(List.of(\"audio\", \"wireless\", \"accessories\")); // 3 tags\n        tags.add(List.of(\"peripherals\", \"computing\"));         // 2 tags\n        // Here m (tags per product) is bounded and small — effectively O(n)\n        printProductsWithTags(products, tags);\n    }\n}",
        "output": "=== Order IDs ===\n  Order: ORD-001\n  Order: ORD-002\n  Order: ORD-003\n=== Order Totals ===\n  $49.99\n  $129.50\n  $18.75\n\n=== Products and Tags ===\n  Laptop → tags: [electronics] [computing] \n  Headphones → tags: [audio] [wireless] [accessories] \n  Keyboard → tags: [peripherals] [computing] "
      }

package io.thecodeforge.complexity;

import java.util.ArrayList;

public class AmortizedArrayListDemo {
    public static void main(String[] args) {
        // Demonstrate that adding many elements is O(n) total, not O(n²)
        int n = 100_000;
        ArrayList<Integer> list = new ArrayList<>();

        long startTime = System.nanoTime();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        long endTime = System.nanoTime();

        long elapsedMs = (endTime - startTime) / 1_000_000;
        System.out.println("Added " + n + " elements in " + elapsedMs + " ms");
        System.out.println("That's amortized O(1) per add — total O(n)");

        // To see the occasional resize, we can check capacity internally (though not public)
        // The point: copying happens only log(n) times, each doubling the array.
    }
}

package io.thecodeforge.complexity;

import java.util.*;

public class InterviewComplexityAnalyzer {

    // Example interview problem: find if any two numbers in an array sum to target
    // Brute force: O(n²) time, O(1) space
    public static boolean hasPairSum_BruteForce(int[] numbers, int target) {\n        for (int i = 0; i < numbers.length; i++) {\n            for (int j = i + 1; j < numbers.length; j++) {\n                if (numbers[i] + numbers[j] == target) {\n                    return true;\n                }
            }
        }
        return false;
    }

    // Optimized: O(n) time, O(n) space using HashSet
    public static boolean hasPairSum_Optimized(int[] numbers, int target) {\n        Set<Integer> seen = new HashSet<>();\n        for (int num : numbers) {\n            int complement = target - num;\n            if (seen.contains(complement)) {\n                return true;\n            }
            seen.add(num);
        }
        return false;
    }

    // For sorted array: O(n log n) due to binary search per element? No