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

// io.thecodeforge — dsa tutorial

public class BinarySearch {
    public static int findCustomer(int[] customerIds, int target) {
        int low = 0;
        int high = customerIds.length - 1;
        int iterations = 0;

        while (low <= high) {
            iterations++;
            int mid = low + (high - low) / 2;
            if (customerIds[mid] == target) {
                System.out.println("Found in " + iterations + " iterations");
                return mid;
            } else if (customerIds[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        System.out.println("Not found after " + iterations + " iterations");
        return -1;
    }

    public static void main(String[] args) {
        int[] ids = {1, 3, 5, 7, 9, 11, 13, 15};
        findCustomer(ids, 13);
    }
}

// io.thecodeforge — dsa tutorial

public class SequentialLoops {
    public static void processOrders(int[] orders) {
        // O(n) — validate each order
        for (int order : orders) {
            if (order <= 0) {
                throw new IllegalArgumentException("Invalid order: " + order);
            }
        }

        // O(n) — apply discount to each order
        for (int i = 0; i < orders.length; i++) {
            orders[i] = (int)(orders[i] * 0.9);
        }

        // O(n log n) — sort orders by value
        java.util.Arrays.sort(orders);
    }

    public static void main(String[] args) {
        int[] customerOrders = {100, 250, 50, 400};
        processOrders(customerOrders);
        System.out.println("Processed orders: " + java.util.Arrays.toString(customerOrders));
    }
}

// io.thecodeforge — dsa tutorial

public class IfElseInLoops {
    public static void processTransactions(int[] amounts) {
        for (int amount : amounts) {
            // This if-else doesn't change O(n) — both branches are O(1)
            if (amount > 1000) {
                logLargeTransaction(amount);
            } else {
                logRegularTransaction(amount);
            }
        }
    }

    private static void logLargeTransaction(int amount) {
        // Simulate writing to a slow audit log — still O(1)
        System.out.println("LARGE: $" + amount);
    }

    private static void logRegularTransaction(int amount) {
        System.out.println("REGULAR: $" + amount);
    }

    public static void main(String[] args) {
        int[] dailyTransactions = {50, 2000, 100, 5000};
        processTransactions(dailyTransactions);
    }
}

// io.thecodeforge — dsa tutorial

// Little o: f = x^1.5 grows strictly slower than g = x^2
public class LittleOExample {
    static double f(int x) { return Math.pow(x, 1.5); }
    static double g(int x) { return Math.pow(x, 2.0); }

    public static void main(String[] args) {
        // For any positive constant c, eventually f(x) < c * g(x)
        double c = 100.0;
        for (int x = 1; x <= 100_000; x *= 10) {
            boolean isLittleO = f(x) < c * g(x);
            System.out.printf("x=%d: f(x)/g(x)=%.6f, f < %.0f*g? %b%n",
                x, f(x)/g(x), c, isLittleO);
        }
    }
}

// io.thecodeforge — dsa tutorial

// Little omega: f = 2^x grows strictly faster than g = x^3
public class LittleOmegaExample {
    static long f(int x) { return (long) Math.pow(2, x); }
    static long g(int x) { return (long) Math.pow(x, 3); }

    public static void main(String[] args) {
        // For any constant c, eventually f(x) > c * g(x)
        double c = 0.5;
        for (int x = 1; x <= 10; x++) {
            boolean isLittleOmega = f(x) > c * g(x);
            System.out.printf("x=%d: f(x)/g(x)=%.2f, f > %.1f*g? %b%n",
                x, (double)f(x)/g(x), c, isLittleOmega);
        }
    }
}