{"title":"Logarithms","description":"","content":"Logarithms come up throughout algorithm analysis. They describe how fast algorithms grow, especially in divide-and-conquer approaches, binary search, and data structures like heaps and trees.\n\nInstead of thinking in terms of \"how big is n,\" logarithms answer a different question: \"how many times can we keep dividing n until we reach 1?\" That perspective is key to understanding why certain algorithms run in O(log n) time and why others scale much more slowly.\n\nIn this chapter, we will build an intuitive understanding of logarithms, connect them to common algorithm patterns, and use practical examples to make them feel natural rather than mathematical.\n\n---\n\n# What is a Logarithm?\n\nA logarithm is the inverse of exponentiation. If you know that:\n\n**2^10 = 1024**\n\nThen the logarithm answers the reverse question: \"What power do I raise 2 to in order to get 1024?\"\n\n**log2(1024) = 10**\n\nMore formally, log_b(x) = y means b^y = x. The base b is the number being raised to a power, x is the result, and y is the exponent we are solving for.\n\n\n| Exponential Form | Logarithmic Form | In Plain English |\n|-----------------|------------------|------------------|\n| 2^3 = 8 | log2(8) = 3 | \"2 multiplied by itself 3 times gives 8\" |\n| 2^10 = 1024 | log2(1024) = 10 | \"You need 10 doublings to reach 1024\" |\n| 10^3 = 1000 | log10(1000) = 3 | \"1000 has 3 zeros, so log base 10 is 3\" |\n| 2^20 = 1,048,576 | log2(1,048,576) = 20 | \"About a million needs 20 halvings\" |\n\n\nIn computer science, the base is almost always 2. That is because computers operate in binary, and most divide-and-conquer algorithms split problems in half at each step.\n\n### The Halving Tree\n\nHere is a visual way to think about logarithms. If you start with 16 elements and keep halving, how many levels does it take to reach 1?\n\n\n```mermaid\nflowchart TD\n A[\"16 elements\"]:::primary --> B[\"8 elements\"]:::teal\n A --> C[\"8 elements\"]:::teal\n B --> D[\"4 elements\"]:::orange\n B --> E[\"4 elements\"]:::orange\n C --> F[\"4 elements\"]:::orange\n C --> G[\"4 elements\"]:::orange\n D --> H[\"2 elements\"]:::green\n D --> I[\"2 elements\"]:::green\n H --> J[\"1 element\"]:::red\n H --> K[\"1 element\"]:::red\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\nThe answer is 4 levels, because log2(16) = 4. Each level represents one halving operation. This is exactly what happens in binary search: at each step, you eliminate half the remaining elements.\n\n---\n\n# Logarithm Rules\n\nThese rules come up in complexity analysis and interview problems. You do not need to memorize proofs, but you should know how to apply each one.\n\n**1. Product Rule: log_b(a * c) = log_b(a) + log_b(c)**\n\nMultiplication inside the log becomes addition outside. This is why the logarithm of a large product can be computed by summing the logarithms of its parts. \n\nFor example:\n\nlog2(32) = log2(8 * 4) = log2(8) + log2(4) = 3 + 2 = 5\n\n**2. Quotient Rule: log_b(a / c) = log_b(a) - log_b(c)**\n\nDivision inside the log becomes subtraction outside.\n\nlog2(8 / 2) = log2(8) - log2(2) = 3 - 1 = 2, which checks out because 8 / 2 = 4 and log2(4) = 2.\n\n**3. Power Rule: log_b(a^n) = n * log_b(a)**\n\nAn exponent inside the log comes out as a multiplier. This one is particularly useful. For example:\n\nlog2(8^3) = 3 * log2(8) = 3 * 3 = 9, and indeed 8^3 = 512 = 2^9.\n\n**4. Change of Base: log_b(a) = log_c(a) / log_c(b)**\n\nThis lets you convert between bases. In most programming languages, the built-in `log` function uses base e (natural log) or base 10. To compute log base 2, you use:\n\nlog2(n) = ln(n) / ln(2), or equivalently, log10(n) / log10(2)\n\n\n> **TIP**\n>\n> In Big-O analysis, the base of the logarithm does not matter. O(log2 n) and O(log10 n) differ only by a constant factor (log2 n = log10 n / log10 2 ≈ 3.32 * log10 n). So we simply write O(log n). However, when computing exact values (like tree height or number of bits), the base absolutely matters.\n\n\n### Why log2 Dominates in Computer Science\n\nMost logarithms you encounter in CS are base 2. The reason is straightforward: the most common algorithmic pattern is dividing a problem into two equal halves.\n\n- **Binary search** eliminates half the array at each step.\n- **Balanced binary trees** split nodes into two subtrees at each level.\n- **Merge sort** divides the array in half, sorts both halves, then merges.\n- **Binary representation** uses base 2, so the number of bits in n is directly related to log2(n).\n\n\n```mermaid\nflowchart LR\n subgraph Patterns[\"Where log2 Appears\"]\n A[\"Binary Search
O(log n)\"]:::primary\n B[\"Balanced BST
Height = log n\"]:::teal\n C[\"Merge Sort
O(n log n)\"]:::orange\n D[\"Heap Operations
O(log n)\"]:::green\n E[\"Bit Counting
floor(log2 n) + 1\"]:::red\n end\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\nOther bases do appear occasionally. Ternary search divides into three parts, giving O(log3 n). B-trees in databases have a branching factor of hundreds, giving O(log_b n) where b might be 100 or more. But since all logarithm bases differ by a constant factor, they are all O(log n) in Big-O notation.\n\n### Floor and Ceiling of Log Values\n\nIn practice, log values are rarely whole numbers. When we need integer results (like tree height or array index), we use floor and ceiling.\n\n- **floor(log2(n))**: the largest integer k such that 2^k <= n\n- **ceil(log2(n))**: the smallest integer k such that 2^k >= n\n\n\n| n | log2(n) | floor(log2(n)) | ceil(log2(n)) |\n|---|---------|----------------|---------------|\n| 1 | 0.0 | 0 | 0 |\n| 2 | 1.0 | 1 | 1 |\n| 3 | 1.58 | 1 | 2 |\n| 7 | 2.81 | 2 | 3 |\n| 8 | 3.0 | 3 | 3 |\n| 10 | 3.32 | 3 | 4 |\n| 16 | 4.0 | 4 | 4 |\n| 100 | 6.64 | 6 | 7 |\n| 1000 | 9.97 | 9 | 10 |\n\n\nUseful formulas that follow from this:\n\n- **Number of bits to represent n** (for n >= 1): floor(log2(n)) + 1\n- **Number of digits in n** (base 10, for n >= 1): floor(log10(n)) + 1\n- **Height of a complete binary tree with n nodes**: floor(log2(n))\n- **Number of levels in binary search on n elements**: floor(log2(n)) + 1\n\n### Connection to Binary Representation\n\nThere is a deep connection between logarithms and binary numbers. The number 13 in binary is 1101, which is 4 bits long. And floor(log2(13)) + 1 = floor(3.7) + 1 = 3 + 1 = 4. This is not a coincidence.\n\nThe highest power of 2 that fits in n determines the most significant bit position. That position is exactly floor(log2(n)), and since we count from position 0, the total number of bits is floor(log2(n)) + 1.\n\n\n```mermaid\nflowchart TB\n A[\"Decimal: 13\"]:::primary --> B[\"Binary: 1101\"]:::teal\n B --> C[\"Bit 3: 1
(2^3 = 8)\"]:::orange\n B --> D[\"Bit 2: 1
(2^2 = 4)\"]:::orange\n B --> E[\"Bit 1: 0
(2^1 = 2)\"]:::primary\n B --> F[\"Bit 0: 1
(2^0 = 1)\"]:::orange\n C --> G[\"floor(log2(13)) = 3
Bits needed = 3 + 1 = 4\"]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n---\n\n# Examples\n\n### Binary Search and log2(n)\n\nLet us trace binary search on a sorted array of 16 elements to see exactly why it takes at most log2(16) = 4 comparisons.\n\n\n```shell\nArray: [2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47]\nTarget: 35\nn = 16, so log2(16) = 4 comparisons expected\n\nStep 1: low=0, high=15, mid=7, arr[7]=23\n 23 < 35, so search right half. Remaining: 8 elements.\n\nStep 2: low=8, high=15, mid=11, arr[11]=35\n 35 == 35, FOUND at index 11.\n\nResult: Found in 2 steps (best case can be fewer than log2(n))\n```\n\n\nNow let us try a worst case, searching for 47 (the last element):\n\n\n```shell\nTarget: 47\n\nStep 1: low=0, high=15, mid=7, arr[7]=23\n 23 < 47, search right. Remaining: 8 elements.\n\nStep 2: low=8, high=15, mid=11, arr[11]=35\n 35 < 47, search right. Remaining: 4 elements.\n\nStep 3: low=12, high=15, mid=13, arr[13]=41\n 41 < 47, search right. Remaining: 2 elements.\n\nStep 4: low=14, high=15, mid=14, arr[14]=44\n 44 < 47, search right. Remaining: 1 element.\n\nStep 5: low=15, high=15, mid=15, arr[15]=47\n 47 == 47, FOUND at index 15.\n\nResult: Found in 5 steps.\n```\n\n\nThis is an important detail. The maximum number of comparisons in binary search on n elements is floor(log2(n)) + 1, not log2(n). The \"+1\" accounts for the final comparison when only one element remains.\n\n### Computing Log Values by Hand\n\nTo build intuition, practice computing log2 values mentally:\n\n- **log2(64)**: 2^6 = 64, so log2(64) = 6\n- **log2(100)**: 2^6 = 64, 2^7 = 128. So log2(100) is between 6 and 7. More precisely, about 6.64.\n- **Number of bits for 100**: floor(6.64) + 1 = 7 bits\n- **Number of decimal digits in 5000**: floor(log10(5000)) + 1 = floor(3.699) + 1 = 4 digits\n\n---\n\n# Implementation\n\nBelow are utility functions. Each implementation provides three functions: computing floor of log base 2, counting the number of decimal digits, and counting the number of bits needed to represent a positive integer.\n\n\n```java\npublic class LogUtils {\n\n // Floor of log base 2 (for n >= 1)\n public static int floorLog2(int n) {\n if (n <= 0) throw new IllegalArgumentException(\"n must be positive\");\n int result = 0;\n while (n > 1) {\n n >>= 1; // equivalent to n = n / 2\n result++;\n }\n return result;\n }\n\n // Number of decimal digits in n (for n >= 1)\n public static int countDigits(int n) {\n if (n <= 0) throw new IllegalArgumentException(\"n must be positive\");\n int count = 0;\n while (n > 0) {\n n /= 10;\n count++;\n }\n return count;\n }\n\n // Number of bits needed to represent n (for n >= 1)\n public static int countBits(int n) {\n if (n <= 0) throw new IllegalArgumentException(\"n must be positive\");\n return floorLog2(n) + 1;\n }\n\n public static void main(String[] args) {\n System.out.println(\"floorLog2(16) = \" + floorLog2(16)); // 4\n System.out.println(\"floorLog2(100) = \" + floorLog2(100)); // 6\n System.out.println(\"countDigits(5000) = \" + countDigits(5000)); // 4\n System.out.println(\"countBits(13) = \" + countBits(13)); // 4\n System.out.println(\"countBits(16) = \" + countBits(16)); // 5\n }\n}\n```\n\n```python\ndef floor_log2(n: int) -> int:\n \"\"\"Floor of log base 2 (for n >= 1).\"\"\"\n if n <= 0:\n raise ValueError(\"n must be positive\")\n result = 0\n while n > 1:\n n >>= 1\n result += 1\n return result\n\ndef count_digits(n: int) -> int:\n \"\"\"Number of decimal digits in n (for n >= 1).\"\"\"\n if n <= 0:\n raise ValueError(\"n must be positive\")\n count = 0\n while n > 0:\n n //= 10\n count += 1\n return count\n\ndef count_bits(n: int) -> int:\n \"\"\"Number of bits needed to represent n (for n >= 1).\"\"\"\n if n <= 0:\n raise ValueError(\"n must be positive\")\n return floor_log2(n) + 1\n\nif __name__ == \"__main__\":\n print(f\"floor_log2(16) = {floor_log2(16)}\") # 4\n print(f\"floor_log2(100) = {floor_log2(100)}\") # 6\n print(f\"count_digits(5000) = {count_digits(5000)}\") # 4\n print(f\"count_bits(13) = {count_bits(13)}\") # 4\n print(f\"count_bits(16) = {count_bits(16)}\") # 5\n```\n\n```cpp\n#include \n#include \n\n// Floor of log base 2 (for n >= 1)\nint floorLog2(int n) {\n if (n <= 0) throw std::invalid_argument(\"n must be positive\");\n int result = 0;\n while (n > 1) {\n n >>= 1;\n result++;\n }\n return result;\n}\n\n// Number of decimal digits in n (for n >= 1)\nint countDigits(int n) {\n if (n <= 0) throw std::invalid_argument(\"n must be positive\");\n int count = 0;\n while (n > 0) {\n n /= 10;\n count++;\n }\n return count;\n}\n\n// Number of bits needed to represent n (for n >= 1)\nint countBits(int n) {\n if (n <= 0) throw std::invalid_argument(\"n must be positive\");\n return floorLog2(n) + 1;\n}\n\nint main() {\n std::cout << \"floorLog2(16) = \" << floorLog2(16) << std::endl; // 4\n std::cout << \"floorLog2(100) = \" << floorLog2(100) << std::endl; // 6\n std::cout << \"countDigits(5000) = \" << countDigits(5000) << std::endl; // 4\n std::cout << \"countBits(13) = \" << countBits(13) << std::endl; // 4\n std::cout << \"countBits(16) = \" << countBits(16) << std::endl; // 5\n return 0;\n}\n```\n\n```go\npackage main\n\nimport (\n\t\"fmt\"\n)\n\n// Floor of log base 2 (for n >= 1)\nfunc floorLog2(n int) int {\n\tif n <= 0 {\n\t\tpanic(\"n must be positive\")\n\t}\n\tresult := 0\n\tfor n > 1 {\n\t\tn >>= 1 // equivalent to n = n / 2\n\t\tresult++\n\t}\n\treturn result\n}\n\n// Number of decimal digits in n (for n >= 1)\nfunc countDigits(n int) int {\n\tif n <= 0 {\n\t\tpanic(\"n must be positive\")\n\t}\n\tcount := 0\n\tfor n > 0 {\n\t\tn /= 10\n\t\tcount++\n\t}\n\treturn count\n}\n\n// Number of bits needed to represent n (for n >= 1)\nfunc countBits(n int) int {\n\tif n <= 0 {\n\t\tpanic(\"n must be positive\")\n\t}\n\treturn floorLog2(n) + 1\n}\n\nfunc main() {\n\tfmt.Println(\"floorLog2(16) =\", floorLog2(16)) // 4\n\tfmt.Println(\"floorLog2(100) =\", floorLog2(100)) // 6\n\tfmt.Println(\"countDigits(5000) =\", countDigits(5000)) // 4\n\tfmt.Println(\"countBits(13) =\", countBits(13)) // 4\n\tfmt.Println(\"countBits(16) =\", countBits(16)) // 5\n}\n```\n\n```csharp\nusing System;\n\npublic class LogUtils\n{\n // Floor of log base 2 (for n >= 1)\n public static int FloorLog2(int n)\n {\n if (n <= 0) throw new ArgumentException(\"n must be positive\");\n int result = 0;\n while (n > 1)\n {\n n >>= 1;\n result++;\n }\n return result;\n }\n\n // Number of decimal digits in n (for n >= 1)\n public static int CountDigits(int n)\n {\n if (n <= 0) throw new ArgumentException(\"n must be positive\");\n int count = 0;\n while (n > 0)\n {\n n /= 10;\n count++;\n }\n return count;\n }\n\n // Number of bits needed to represent n (for n >= 1)\n public static int CountBits(int n)\n {\n if (n <= 0) throw new ArgumentException(\"n must be positive\");\n return FloorLog2(n) + 1;\n }\n\n public static void Main(string[] args)\n {\n Console.WriteLine($\"FloorLog2(16) = {FloorLog2(16)}\"); // 4\n Console.WriteLine($\"FloorLog2(100) = {FloorLog2(100)}\"); // 6\n Console.WriteLine($\"CountDigits(5000) = {CountDigits(5000)}\"); // 4\n Console.WriteLine($\"CountBits(13) = {CountBits(13)}\"); // 4\n Console.WriteLine($\"CountBits(16) = {CountBits(16)}\"); // 5\n }\n}\n```\n\n```rust\nuse std::panic;\n\npub struct LogUtils;\n\nimpl LogUtils {\n // Floor of log base 2 (for n >= 1)\n pub fn floor_log2(mut n: i32) -> i32 {\n if n <= 0 {\n panic!(\"n must be positive\");\n }\n let mut result = 0;\n while n > 1 {\n n >>= 1; // equivalent to n = n / 2\n result += 1;\n }\n result\n }\n\n // Number of decimal digits in n (for n >= 1)\n pub fn count_digits(mut n: i32) -> i32 {\n if n <= 0 {\n panic!(\"n must be positive\");\n }\n let mut count = 0;\n while n > 0 {\n n /= 10;\n count += 1;\n }\n count\n }\n\n // Number of bits needed to represent n (for n >= 1)\n pub fn count_bits(n: i32) -> i32 {\n if n <= 0 {\n panic!(\"n must be positive\");\n }\n Self::floor_log2(n) + 1\n }\n}\n\nfn main() {\n println!(\"floorLog2(16) = {}\", LogUtils::floor_log2(16)); // 4\n println!(\"floorLog2(100) = {}\", LogUtils::floor_log2(100)); // 6\n println!(\"countDigits(5000) = {}\", LogUtils::count_digits(5000)); // 4\n println!(\"countBits(13) = {}\", LogUtils::count_bits(13)); // 4\n println!(\"countBits(16) = {}\", LogUtils::count_bits(16)); // 5\n}\n```\n\n```javascript\n// Floor of log base 2 (for n >= 1)\nfunction floorLog2(n) {\n if (n <= 0) throw new Error(\"n must be positive\");\n let result = 0;\n while (n > 1) {\n n >>= 1;\n result++;\n }\n return result;\n}\n\n// Number of decimal digits in n (for n >= 1)\nfunction countDigits(n) {\n if (n <= 0) throw new Error(\"n must be positive\");\n let count = 0;\n while (n > 0) {\n n = Math.floor(n / 10);\n count++;\n }\n return count;\n}\n\n// Number of bits needed to represent n (for n >= 1)\nfunction countBits(n) {\n if (n <= 0) throw new Error(\"n must be positive\");\n return floorLog2(n) + 1;\n}\n\nconsole.log(`floorLog2(16) = ${floorLog2(16)}`); // 4\nconsole.log(`floorLog2(100) = ${floorLog2(100)}`); // 6\nconsole.log(`countDigits(5000) = ${countDigits(5000)}`); // 4\nconsole.log(`countBits(13) = ${countBits(13)}`); // 4\nconsole.log(`countBits(16) = ${countBits(16)}`); // 5\n```\n\n```typescript\n// Floor of log base 2 (for n >= 1)\nfunction floorLog2(n: number): number {\n if (n <= 0) throw new Error(\"n must be positive\");\n let result: number = 0;\n while (n > 1) {\n n >>= 1;\n result++;\n }\n return result;\n}\n\n// Number of decimal digits in n (for n >= 1)\nfunction countDigits(n: number): number {\n if (n <= 0) throw new Error(\"n must be positive\");\n let count: number = 0;\n while (n > 0) {\n n = Math.floor(n / 10);\n count++;\n }\n return count;\n}\n\n// Number of bits needed to represent n (for n >= 1)\nfunction countBits(n: number): number {\n if (n <= 0) throw new Error(\"n must be positive\");\n return floorLog2(n) + 1;\n}\n\nconsole.log(`floorLog2(16) = ${floorLog2(16)}`); // 4\nconsole.log(`floorLog2(100) = ${floorLog2(100)}`); // 6\nconsole.log(`countDigits(5000) = ${countDigits(5000)}`); // 4\nconsole.log(`countBits(13) = ${countBits(13)}`); // 4\nconsole.log(`countBits(16) = ${countBits(16)}`); // 5\n```\n\n\nNote that all implementations use bit shifting (`n >>= 1`) instead of division for the log2 computation. This is both faster and more idiomatic when working with powers of 2. The loop counts how many times we can right-shift n before it becomes 1, which is exactly the definition of floor(log2(n)).","pageType":"dsa"}

Logarithms

Get Premium