[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":86,"_72":87,"_35":88},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":16,"_64":65,"_66":67,"_68":69,"_70":71},"id",28,"title","Algorithm Analysis Fundamentals","slug","algorithms-part-1-algorithm-analysis-fundamentals","excerpt","Master Big O notation, Big Omega, Big Theta, and amortized analysis. Learn to derive complexity for any algorithm and use JMH for proper Java benchmarking.","# Algorithms Compendium Part 1: Algorithm Analysis Fundamentals\n\nUnderstanding algorithm complexity is the single most important skill that separates developers who write code from engineers who write scalable systems. This article provides the foundation for everything that follows in this series - a deep understanding of Big O notation, asymptotic analysis, and practical benchmarking in Java.\n\nIn this article, we'll go beyond the surface-level \"memorize the Big O table\" approach and build true intuition for how to analyze any algorithm.\n\n## 📋 At a Glance\n\n| Aspect | Details |\n|--------|---------|\n| Core Concepts | Big O, Big Omega, Big Theta, Amortized Analysis |\n| Key Skills | Complexity derivation, JMH benchmarking, space/time trade-offs |\n| Common Complexities | O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) |\n| JDK Tools | System.nanoTime(), JMH (Java Microbenchmark Harness) |\n| Key Insight | Big O describes growth rate, not actual speed |\n\n---\n\n## 🎯 What You'll Learn\n\nAfter reading this article, you will be able to:\n\n- **Derive Big O complexity** for any algorithm by counting operations\n- **Distinguish between Big O, Omega, and Theta** and when each applies\n- **Apply amortized analysis** to understand ArrayList's true O(1) add\n- **Benchmark Java code properly** using JMH to avoid common pitfalls\n- **Analyze space complexity** alongside time complexity\n- **Recognize hidden complexity** in seemingly innocent code\n\n---\n\n## 🔥 Production Story: The Hidden O(n²)\n\nA logistics company had a route optimization service that worked perfectly during testing. When deployed to production, it collapsed under load.\n\nThe team investigated and found this innocent-looking code:\n\n```java\n// ❌ The \"simple\" validation logic\npublic void validateOrders(List orders) {\n for (Order order : orders) {\n if (!isValidDestination(order.getDestination())) {\n throw new InvalidOrderException(order.getId());\n }\n }\n}\n\nprivate boolean isValidDestination(String destination) {\n // Check against valid destinations\n return validDestinations.contains(destination);\n}\n```\n\n\"It's O(n),\" the team said. \"We iterate once through orders.\"\n\n**What they missed:**\n\n```java\n// ❌ validDestinations was a List\nprivate List validDestinations = loadValidDestinations();\n\n// List.contains() is O(n)!\n// So the total complexity is O(n) × O(m) = O(n × m)\n// With 10,000 orders and 5,000 destinations: 50,000,000 operations\n```\n\n**The fix:**\n\n```java\n// ✅ Change List to Set\nprivate Set validDestinations = new HashSet<>(loadValidDestinations());\n\n// Set.contains() is O(1)\n// Total complexity: O(n) × O(1) = O(n)\n// With 10,000 orders: 10,000 operations\n```\n\n**Result:** Response time dropped from 12 seconds to 15 milliseconds.\n\n### 🎮 How Hash Tables Work\n\nSee how a hash table achieves O(1) lookups using hashing and handles collisions:\n\n```visualizer-hashtable\ncontrols: true\n```\n\n**The lesson:** Hidden complexity lurks in every method call. Understanding what operations cost is not academic - it's essential for production systems.\n\n---\n\n## 🧠 Mental Model: The Growth Rate Perspective\n\n### Big O Is About Growth, Not Speed\n\nA common misconception: \"O(n) is faster than O(n²).\"\n\n**Not always true.** Consider:\n\n```java\n// Algorithm A: O(n) but slow constant factor\nvoid algorithmA(int[] arr) {\n for (int i = 0; i < arr.length; i++) {\n expensiveOperation(); // Takes 1000ms\n expensiveOperation();\n expensiveOperation();\n }\n}\n\n// Algorithm B: O(n²) but fast constant factor\nvoid algorithmB(int[] arr) {\n for (int i = 0; i < arr.length; i++) {\n for (int j = 0; j < arr.length; j++) {\n cheapOperation(); // Takes 0.001ms\n }\n }\n}\n```\n\n**For small n:**\n- Algorithm A (n=10): 10 × 3000ms = 30,000ms\n- Algorithm B (n=10): 100 × 0.001ms = 0.1ms\n\nAlgorithm B wins by a factor of 300,000!\n\n**For large n:**\n- Algorithm A (n=10,000): 10,000 × 3000ms = 30,000 seconds\n- Algorithm B (n=10,000): 100,000,000 × 0.001ms = 100,000 seconds\n\nAlgorithm A wins!\n\n**The insight:** Big O tells you how the algorithm *scales*. For choosing between algorithms, consider:\n1. Expected input size\n2. Constant factors\n3. Real-world benchmarks\n\n### Visualizing Growth Rates\n\n```text\nOperations\n ^\n | 2^n\n | .·'\n | .·'\n | .·'\n | n² .·'\n | .·'.·'···'\n | .·'\n | .·' n log n\n | .·' .·'····\n | .·' .·'····\n | .·' .·'··\n | .·' .·'· n\n | .·'.·'·······\n | .·'··· log n\n | .'..·····························\n |___________________________________|_______> n\n Input Size\n\nGrowth Rate Comparison (at n = 1,000,000):\n├── O(1): 1 operation\n├── O(log n): 20 operations\n├── O(n): 1,000,000 operations\n├── O(n log n): 20,000,000 operations\n├── O(n²): 1,000,000,000,000 operations\n└── O(2ⁿ): 2^1000000 operations (universe heat death)\n```\n\n---\n\n## 🔬 Deep Dive\n\n### 1. Big O, Omega, and Theta: The Complete Picture\n\nMost developers know only Big O. But there are three asymptotic notations:\n\n```text\n┌─────────────────────────────────────────────────────────────┐\n│ ASYMPTOTIC NOTATION │\n├─────────────────────────────────────────────────────────────┤\n│ │\n│ O(g(n)) - Upper Bound │\n│ \"At most\" - worst case won't exceed this │\n│ f(n) ≤ c × g(n) for large n │\n│ │\n│ Ω(g(n)) - Lower Bound (Omega) │\n│ \"At least\" - best case won't be better than this │\n│ f(n) ≥ c × g(n) for large n │\n│ │\n│ Θ(g(n)) - Tight Bound (Theta) │\n│ \"Exactly\" - both upper and lower │\n│ c₁ × g(n) ≤ f(n) ≤ c₂ × g(n) for large n │\n│ │\n└─────────────────────────────────────────────────────────────┘\n```\n\n**Practical example - Binary Search:**\n\n```java\n// ✅ Binary Search complexity analysis\npublic int binarySearch(int[] arr, int target) {\n int low = 0, high = arr.length - 1;\n\n while (low <= high) {\n int mid = low + (high - low) / 2; // Avoids overflow\n\n if (arr[mid] == target) {\n return mid; // Best case: first comparison\n } else if (arr[mid] < target) {\n low = mid + 1;\n } else {\n high = mid - 1;\n }\n }\n return -1; // Worst case: log n comparisons\n}\n```\n\n**Complexity analysis:**\n- **Best case Ω(1)**: Target is at the middle\n- **Worst case O(log n)**: Target doesn't exist or is at the end\n- **Tight bound Θ(log n)**: Average case is also logarithmic\n\n**When to use which:**\n- Use **O(n)** when discussing worst-case guarantees (most common)\n- Use **Ω(n)** when proving lower bounds or best-case\n- Use **Θ(n)** when average and worst case are the same\n\n### 2. Counting Operations: The Derivation Process\n\nTo derive Big O, count the dominant operations as a function of input size.\n\n**Step-by-step example:**\n\n```java\n// ❓ What's the Big O?\npublic int findMax(int[] arr) {\n int max = arr[0]; // 1 operation\n for (int i = 1; i < arr.length; i++) { // Loop runs (n-1) times\n if (arr[i] > max) { // 1 comparison per iteration\n max = arr[i]; // At most (n-1) assignments\n }\n }\n return max; // 1 operation\n}\n```\n\n**Count:**\n- Initializations: 2 (constant)\n- Loop iterations: n - 1\n- Comparisons: n - 1\n- Assignments: at most n - 1\n\n**Total:** 2 + 3(n-1) = 3n - 1\n\n**Simplification rules:**\n1. Drop constants: 3n → n\n2. Drop lower-order terms: 3n - 1 → n\n\n**Result:** O(n)\n\n**More complex example:**\n\n```java\n// ❓ Nested loops - what's the complexity?\npublic void printPairs(int[] arr) {\n for (int i = 0; i < arr.length; i++) { // n iterations\n for (int j = i + 1; j < arr.length; j++) { // ? iterations\n System.out.println(arr[i] + \", \" + arr[j]);\n }\n }\n}\n```\n\n**Inner loop count:**\n- When i = 0: j goes 1 to n-1 → (n-1) iterations\n- When i = 1: j goes 2 to n-1 → (n-2) iterations\n- When i = n-2: j goes n-1 to n-1 → 1 iteration\n- When i = n-1: j doesn't run → 0 iterations\n\n**Total:** (n-1) + (n-2) + ... + 1 + 0 = n(n-1)/2 = (n² - n)/2\n\n**Simplified:** O(n²)\n\n### 3. Amortized Analysis: The ArrayList Mystery\n\nStandard analysis says ArrayList's `add()` is O(n) because it might resize. But we claim O(1) amortized. How?\n\n```java\n// ✅ ArrayList resize behavior (simplified)\npublic class SimpleArrayList {\n private Object[] elements;\n private int size = 0;\n\n public void add(E element) {\n if (size == elements.length) {\n // Double the capacity - O(n) operation\n Object[] newElements = new Object[elements.length * 2];\n System.arraycopy(elements, 0, newElements, 0, size);\n elements = newElements;\n }\n elements[size++] = element; // O(1) operation\n }\n}\n```\n\n**Amortized analysis using the accounting method:**\n\nImagine each add() operation pays 3 \"coins\":\n- 1 coin to add the element\n- 2 coins saved for future resize work\n\nWhen resize happens at capacity n:\n- We need n coins to copy n elements\n- We've saved 2 coins per element since last resize (n/2 elements)\n- Total saved: n coins - exactly what we need!\n\n```text\nCapacity: 1 → 2 → 4 → 8 → 16\nAdds: 1 2 4 8 16\nResizes at: 2 4 8 16 32\nCopy cost: 1 2 4 8 16\n\nTotal operations for n adds:\nn adds × 1 = n\n+ copying at resize: 1 + 2 + 4 + 8 + ... + n/2 = n - 1\n\nTotal: n + (n-1) = 2n - 1\n\nAmortized per add: (2n-1)/n ≈ 2 = O(1)\n```\n\n### 4. Space Complexity: The Other Dimension\n\nTime isn't everything. Memory matters too.\n\n```java\n// ✅ O(n) time, O(n) space\npublic int[] reverseWithCopy(int[] arr) {\n int[] result = new int[arr.length]; // O(n) extra space\n for (int i = 0; i < arr.length; i++) {\n result[arr.length - 1 - i] = arr[i];\n }\n return result;\n}\n\n// ✅ O(n) time, O(1) space - in-place\npublic void reverseInPlace(int[] arr) {\n int left = 0, right = arr.length - 1;\n while (left < right) {\n // Swap using XOR - no extra variable needed\n arr[left] ^= arr[right];\n arr[right] ^= arr[left];\n arr[left] ^= arr[right];\n left++;\n right--;\n }\n}\n```\n\n**Space complexity considerations:**\n- Input space doesn't count (it's given)\n- Auxiliary space is what we analyze\n- Recursive call stack counts!\n\n```java\n// ✅ O(n) time, O(n) space due to recursion stack\npublic int factorial(int n) {\n if (n <= 1) return 1;\n return n * factorial(n - 1); // Each call adds to stack\n}\n\n// ✅ O(n) time, O(1) space - iterative\npublic int factorialIterative(int n) {\n int result = 1;\n for (int i = 2; i <= n; i++) {\n result *= i;\n }\n return result;\n}\n```\n\n### 5. JMH Benchmarking: Measuring Real Performance\n\nNaive benchmarking in Java is unreliable due to JIT compilation, warmup, and garbage collection. Use JMH (Java Microbenchmark Harness).\n\n**Setup (add to pom.xml or build.gradle):**\n\n```xml\n\n org.openjdk.jmh\n jmh-core\n 1.37\n\n\n org.openjdk.jmh\n jmh-generator-annprocess\n 1.37\n\n```\n\n**Benchmark example:**\n\n```java\nimport org.openjdk.jmh.annotations.*;\nimport java.util.concurrent.TimeUnit;\n\n@BenchmarkMode(Mode.AverageTime)\n@OutputTimeUnit(TimeUnit.NANOSECONDS)\n@State(Scope.Benchmark)\n@Warmup(iterations = 5, time = 1)\n@Measurement(iterations = 10, time = 1)\n@Fork(2)\npublic class SearchBenchmark {\n\n @Param({\"100\", \"1000\", \"10000\", \"100000\"})\n private int size;\n\n private int[] sortedArray;\n private int target;\n\n @Setup\n public void setup() {\n sortedArray = new int[size];\n for (int i = 0; i < size; i++) {\n sortedArray[i] = i * 2;\n }\n target = size - 1; // Near the end\n }\n\n @Benchmark\n public int linearSearch() {\n for (int i = 0; i < sortedArray.length; i++) {\n if (sortedArray[i] == target) return i;\n }\n return -1;\n }\n\n @Benchmark\n public int binarySearch() {\n int low = 0, high = sortedArray.length - 1;\n while (low <= high) {\n int mid = low + (high - low) / 2;\n if (sortedArray[mid] == target) return mid;\n else if (sortedArray[mid] < target) low = mid + 1;\n else high = mid - 1;\n }\n return -1;\n }\n}\n```\n\n**Expected results:**\n\n```text\nBenchmark (size) Mode Cnt Score Error Units\nSearchBenchmark.linearSearch 100 avgt 20 52.341 ± 0.812 ns/op\nSearchBenchmark.linearSearch 1000 avgt 20 498.123 ± 5.231 ns/op\nSearchBenchmark.linearSearch 10000 avgt 20 4912.456 ± 28.45 ns/op\nSearchBenchmark.linearSearch 100000 avgt 20 49234.789 ± 312.1 ns/op\nSearchBenchmark.binarySearch 100 avgt 20 18.234 ± 0.123 ns/op\nSearchBenchmark.binarySearch 1000 avgt 20 24.567 ± 0.234 ns/op\nSearchBenchmark.binarySearch 10000 avgt 20 31.234 ± 0.345 ns/op\nSearchBenchmark.binarySearch 100000 avgt 20 38.901 ± 0.456 ns/op\n```\n\n**Observations:**\n- Linear search: ~10x time for 10x data (confirms O(n))\n- Binary search: barely increases (confirms O(log n))\n- At n=100: linear is only 3x slower (constant factors!)\n- At n=100000: linear is 1000x slower (growth rate dominates!)\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Ignoring Method Complexity\n\n```java\n// ❌ Looks O(n), actually O(n²)\npublic void processItems(List items) {\n for (Item item : items) { // O(n)\n if (items.contains(item)) { // O(n) for ArrayList!\n process(item);\n }\n }\n}\n// Total: O(n) × O(n) = O(n²)\n\n// ✅ Use Set for O(1) contains\npublic void processItemsOptimized(List items) {\n Set itemSet = new HashSet<>(items); // O(n) one-time\n for (Item item : items) { // O(n)\n if (itemSet.contains(item)) { // O(1)\n process(item);\n }\n }\n}\n// Total: O(n) + O(n) × O(1) = O(n)\n```\n\n### Mistake 2: Forgetting String Concatenation Cost\n\n```java\n// ❌ String concatenation in loop: O(n²)\npublic String buildString(List parts) {\n String result = \"\";\n for (String part : parts) { // O(n) iterations\n result += part; // O(k) where k grows with each concat\n }\n return result;\n}\n// Each += creates a new String and copies all previous chars\n// Total: 1 + 2 + 3 + ... + n = n(n+1)/2 = O(n²)\n\n// ✅ StringBuilder: O(n)\npublic String buildStringOptimized(List parts) {\n StringBuilder sb = new StringBuilder();\n for (String part : parts) {\n sb.append(part); // Amortized O(1)\n }\n return sb.toString();\n}\n```\n\n### Mistake 3: Misunderstanding Logarithms\n\n```java\n// Common confusion: What base is log in O(log n)?\n\n// Answer: It doesn't matter!\n// log₂(n) = log₁₀(n) / log₁₀(2) = log₁₀(n) × constant\n\n// All logarithms differ only by a constant factor\n// O(log₂ n) = O(log₁₀ n) = O(ln n) = O(log n)\n```\n\n---\n\n## 🐛 Debug This\n\nThe following code has a hidden complexity issue. Find it:\n\n```java\npublic class OrderProcessor {\n private List processedOrders = new ArrayList<>();\n\n public void processOrder(Order order) {\n // Validate order doesn't already exist\n if (processedOrders.contains(order)) {\n throw new DuplicateOrderException(order.getId());\n }\n\n // Process the order\n doBusinessLogic(order);\n\n // Add to processed list\n processedOrders.add(order);\n }\n\n public void batchProcess(List orders) {\n for (Order order : orders) {\n processOrder(order);\n }\n }\n}\n```\n\n**Hint:** What's the complexity of `batchProcess()` for n orders?\n\n

Click to reveal the bug and solution

\n\n**The Bug:**\n\n`processedOrders.contains(order)` is O(k) where k is the number of already processed orders.\n\nFor the i-th order, contains checks against (i-1) orders.\n\nTotal: 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 = **O(n²)**\n\n**The Fix:**\n\n```java\npublic class OrderProcessor {\n private Set processedOrders = new HashSet<>();\n private List processedOrdersList = new ArrayList<>(); // If order matters\n\n public void processOrder(Order order) {\n if (processedOrders.contains(order)) { // O(1)\n throw new DuplicateOrderException(order.getId());\n }\n\n doBusinessLogic(order);\n\n processedOrders.add(order); // O(1)\n processedOrdersList.add(order); // O(1) amortized\n }\n}\n```\n\nNow `batchProcess()` is O(n).\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Derive the Complexity ⭐\n\nWhat is the Big O of this function?\n\n```java\npublic void mystery(int n) {\n for (int i = 1; i < n; i *= 2) {\n for (int j = 0; j < i; j++) {\n System.out.println(i + \", \" + j);\n }\n }\n}\n```\n\n

Solution

\n\n**Outer loop:** i takes values 1, 2, 4, 8, ..., until i ≥ n\nNumber of iterations: log₂(n)\n\n**Inner loop iterations:**\n- When i = 1: 1 iteration\n- When i = 2: 2 iterations\n- When i = 4: 4 iterations\n- ...\n- When i = n/2: n/2 iterations\n\n**Total:** 1 + 2 + 4 + ... + n/2 = n - 1 (geometric series)\n\n**Answer: O(n)**\n\nSurprising! Despite nested loops, this is linear because the inner work grows geometrically while outer iterations grow logarithmically.\n

\n\n---\n\n### Exercise 2: Fix the Performance ⭐⭐\n\nThe following code finds common elements between two lists. It's too slow. Fix it.\n\n```java\npublic List findCommon(List list1, List list2) {\n List result = new ArrayList<>();\n for (Integer num : list1) {\n if (list2.contains(num) && !result.contains(num)) {\n result.add(num);\n }\n }\n return result;\n}\n```\n\n

Solution

\n\n**Current complexity:** O(n × m × r) where n=list1.size(), m=list2.size(), r=result.size()\n\n**Optimized:**\n\n```java\npublic List findCommonOptimized(List list1, List list2) {\n Set set2 = new HashSet<>(list2); // O(m)\n Set seen = new HashSet<>();\n List result = new ArrayList<>();\n\n for (Integer num : list1) { // O(n)\n if (set2.contains(num) && !seen.contains(num)) { // O(1) + O(1)\n result.add(num);\n seen.add(num);\n }\n }\n return result;\n}\n```\n\n**New complexity:** O(n + m)\n

\n\n---\n\n### Exercise 3: Analyze Recursive Complexity ⭐⭐\n\nWhat is the time and space complexity?\n\n```java\npublic int fib(int n) {\n if (n <= 1) return n;\n return fib(n - 1) + fib(n - 2);\n}\n```\n\n

Solution

\n\n**Time complexity:** O(2ⁿ)\n\nEach call spawns two calls. The recursion tree has ~2ⁿ nodes.\n\n```text\n fib(5)\n / \\\n fib(4) fib(3)\n / \\ / \\\n fib(3) fib(2) fib(2) fib(1)\n / \\\n fib(2) fib(1)\n```\n\n**Space complexity:** O(n)\n\nMaximum depth of recursion = n (the call stack).\n\n**Optimized with memoization:** O(n) time, O(n) space\n\n```java\npublic int fibMemo(int n, int[] memo) {\n if (n <= 1) return n;\n if (memo[n] != 0) return memo[n];\n memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);\n return memo[n];\n}\n```\n

\n\n---\n\n### Exercise 4: Write a JMH Benchmark ⭐⭐⭐\n\nWrite a JMH benchmark comparing `ArrayList.get(i)` vs `LinkedList.get(i)` for random access patterns.\n\n

Solution

\n\n```java\n@BenchmarkMode(Mode.AverageTime)\n@OutputTimeUnit(TimeUnit.NANOSECONDS)\n@State(Scope.Benchmark)\n@Warmup(iterations = 5, time = 1)\n@Measurement(iterations = 10, time = 1)\n@Fork(2)\npublic class ListAccessBenchmark {\n\n @Param({\"100\", \"1000\", \"10000\"})\n private int size;\n\n private List arrayList;\n private List linkedList;\n private int[] accessPattern;\n\n @Setup\n public void setup() {\n arrayList = new ArrayList<>();\n linkedList = new LinkedList<>();\n\n for (int i = 0; i < size; i++) {\n arrayList.add(i);\n linkedList.add(i);\n }\n\n // Random access pattern\n Random random = new Random(42);\n accessPattern = new int[100];\n for (int i = 0; i < 100; i++) {\n accessPattern[i] = random.nextInt(size);\n }\n }\n\n @Benchmark\n public int arrayListAccess() {\n int sum = 0;\n for (int idx : accessPattern) {\n sum += arrayList.get(idx);\n }\n return sum;\n }\n\n @Benchmark\n public int linkedListAccess() {\n int sum = 0;\n for (int idx : accessPattern) {\n sum += linkedList.get(idx);\n }\n return sum;\n }\n}\n```\n\nExpected: LinkedList gets dramatically slower as size increases (O(n) per access vs O(1)).\n

\n\n---\n\n### Exercise 5: Master Theorem Application ⭐⭐⭐⭐\n\nGiven the recurrence relation T(n) = 2T(n/2) + O(n), derive the complexity using the Master Theorem.\n\n

Solution

\n\n**Master Theorem:** For recurrence T(n) = aT(n/b) + f(n)\n\nCompare f(n) with n^(log_b(a)):\n\nIn our case: a=2, b=2, f(n)=n\n\nn^(log₂(2)) = n^1 = n\n\nSince f(n) = Θ(n^(log_b(a))) = Θ(n), we're in **Case 2**.\n\n**Result:** T(n) = Θ(n log n)\n\nThis is the recurrence for **MergeSort**:\n- 2 subproblems of half the size\n- O(n) work to merge\n- Total: O(n log n)\n

\n\n---\n\n## 🎤 Interview Questions\n\n### Question #1: What's the difference between O(1) and O(n) for HashMap operations?\n\n**What interviewers want to hear**: Understanding of hash collisions and worst-case scenarios.\n\n**Strong answer**:\nHashMap operations are O(1) *average* case with a good hash function and load factor. However:\n- **Worst case is O(n)** when all keys hash to the same bucket (before Java 8)\n- **Java 8+ improved to O(log n)** worst case by converting long collision chains to balanced trees\n- The amortized O(1) assumes proper equals/hashCode implementation and reasonable load factor (default 0.75)\n\n---\n\n### Question #2: How would you prove that comparison-based sorting cannot be faster than O(n log n)?\n\n**What interviewers want to hear**: Understanding of decision trees and lower bounds.\n\n**Strong answer**:\nAny comparison-based sort can be viewed as a decision tree where each internal node is a comparison and leaves represent sorted permutations.\n\n- There are n! possible permutations of n elements\n- A binary tree with L leaves has height at least log₂(L)\n- Therefore, height ≥ log₂(n!) ≈ n log n (by Stirling's approximation)\n- Height = number of comparisons in worst case\n\nThis proves Ω(n log n) is a lower bound for comparison sorts. Algorithms like Counting Sort beat this by not using comparisons.\n\n---\n\n### Question #3: Explain amortized analysis with a practical example.\n\n**What interviewers want to hear**: Clear explanation with a concrete example.\n\n**Strong answer**:\nAmortized analysis gives the average cost per operation over a worst-case sequence of operations.\n\n**Example: Dynamic Array (ArrayList)**\n- Most `add()` operations are O(1)\n- Occasionally, when capacity is full, resize copies all n elements: O(n)\n\nUsing accounting method:\n- Each add pays 3 tokens\n- 1 token to add the element\n- 2 tokens saved for future copying\n\nWhen we resize from capacity n to 2n:\n- We've added n/2 elements since last resize\n- Each saved 2 tokens = n tokens total\n- Copying n elements costs n tokens\n\nCost is \"prepaid\" by previous operations, so amortized cost per add is O(1).\n\n---\n\n### Question #4: Why is System.nanoTime() unreliable for benchmarking?\n\n**What interviewers want to hear**: Understanding of JVM internals and proper benchmarking.\n\n**Strong answer**:\nSeveral factors make naive timing unreliable:\n\n1. **JIT compilation**: Code runs slower until JIT compiles it. First iterations are not representative.\n\n2. **Warmup**: JVM optimizes hot paths over time. Early measurements don't reflect steady-state.\n\n3. **Dead code elimination**: JVM may optimize away code whose result isn't used.\n\n4. **Garbage collection**: Random GC pauses add noise.\n\n5. **CPU frequency scaling**: Modern CPUs vary clock speed.\n\n**Solution**: Use JMH, which handles warmup, prevents dead code elimination via `Blackhole`, runs multiple forks, and provides statistical analysis.\n\n---\n\n### Question #5: How do you analyze the complexity of recursive algorithms?\n\n**What interviewers want to hear**: Systematic approach with multiple techniques.\n\n**Strong answer**:\nThree main approaches:\n\n1. **Substitution method**: Guess the answer, prove by induction\n - Good when you have intuition about the answer\n\n2. **Recursion tree method**: Draw the tree of recursive calls\n - Sum work at each level\n - Count levels\n - Good for building intuition\n\n3. **Master theorem**: For recurrences T(n) = aT(n/b) + f(n)\n - Compare f(n) with n^(log_b(a))\n - Three cases give the answer directly\n - Fast but only works for specific forms\n\n**Example**: MergeSort T(n) = 2T(n/2) + n\n- Recursion tree: log n levels, each level does O(n) work\n- Master theorem: Case 2 applies\n- Both give T(n) = O(n log n)\n\n---\n\n## 📋 Quick Reference\n\n### Complexity Classes\n\n| Notation | Name | Example | Practical Limit |\n|----------|------|---------|-----------------|\n| O(1) | Constant | Array access | Any |\n| O(log n) | Logarithmic | Binary search | Billions |\n| O(n) | Linear | Find max | Millions |\n| O(n log n) | Linearithmic | MergeSort | Millions |\n| O(n²) | Quadratic | Bubble sort | ~10,000 |\n| O(n³) | Cubic | Matrix multiply | ~1,000 |\n| O(2ⁿ) | Exponential | Subsets | ~25 |\n| O(n!) | Factorial | Permutations | ~12 |\n\n### Analysis Checklist\n\n1. **Identify loops**: Nested loops often multiply\n2. **Check method calls**: contains(), indexOf(), substring() have costs\n3. **Count recursive calls**: Draw the recursion tree\n4. **Consider data structures**: List.contains() ≠ Set.contains()\n5. **Don't forget space**: Recursive stack, intermediate copies\n\n### JMH Quick Setup\n\n```java\n@BenchmarkMode(Mode.AverageTime)\n@OutputTimeUnit(TimeUnit.NANOSECONDS)\n@Warmup(iterations = 5)\n@Measurement(iterations = 10)\n@Fork(2)\npublic class MyBenchmark {\n @Benchmark\n public void testMethod(Blackhole bh) {\n bh.consume(resultToPreventDeadCode);\n }\n}\n```\n\n---\n\n## 📝 Summary & Key Takeaways\n\n### Core Principles\n\n1. **Big O describes growth rate**, not actual speed\n2. **Always analyze hidden method complexity** - contains(), indexOf() have costs\n3. **Amortized analysis explains dynamic structures** - ArrayList's O(1) add\n4. **Use JMH for reliable benchmarks** - naive timing is unreliable\n5. **Space complexity matters too** - recursive calls use stack\n\n### What You Can Do Now\n\n- Derive Big O for any iterative algorithm by counting operations\n- Spot hidden O(n²) patterns in production code\n- Use JMH to benchmark Java code properly\n- Apply amortized analysis to understand dynamic data structures\n- Explain complexity trade-offs in technical discussions\n\n---\n\n## 📅 Review Schedule\n\n| Day | Task | Time |\n|-----|------|------|\n| Day 1 | Review At a Glance + Quick Reference | 5 min |\n| Day 3 | Redo Exercise 1 and 2 | 15 min |\n| Day 7 | Derive complexity of a random algorithm | 10 min |\n| Day 14 | Redo Debug This exercise | 10 min |\n| Day 30 | Answer interview questions aloud | 15 min |\n\n---\n\n*Next in series: [Part 2: Recursion & Iteration Mastery - Call Stack, TCO & Conversion Patterns]*\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.010368Z","createdAt","2026-06-10T07:19:25.011049Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",17,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder","author",{"_31":55,"_102":57,"_103":104,"_105":106,"_107":-5,"_108":-5,"_109":-5,"_110":-5,"_111":-5},"category",{"_31":98,"_72":59,"_35":99,"_75":100,"_101":-5},"tags",[78,79,80,81,82],"series",{"_31":62,"_72":73,"_35":74,"_75":76,"_77":23},"name","Algorithms Compendium: From Theory to Production","algorithms-compendium","description","A comprehensive 23-part series covering all essential algorithms for Java developers. From foundational concepts like complexity analysis and recursion, through sorting (QuickSort, MergeSort, TimSort), searching (binary search, string matching), graph algorithms (DFS, BFS, Dijkstra, MST), dynamic programming, greedy algorithms, backtracking, to probabilistic data structures (Bloom filters, HyperLogLog) and interview patterns. Includes real production stories, mental models, exercises, and 100+ interview questions.","isActive",{"_31":95,"_72":96,"_35":97},{"_31":92,"_72":93,"_35":94},{"_31":89,"_72":90,"_35":91},{"_31":86,"_72":87,"_35":88},{"_31":83,"_72":84,"_35":85},122,"Jmh","jmh",120,"Complexity","complexity",119,"Big-o","big-o",123,"Benchmarking","benchmarking",121,"Analysis","analysis",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]