Functions, Growth and Logarithms

Table of Contents

1. A Function Is an Input-to-Output Machine
2. Three Shapes of Growth
3. Powers and Exponents
4. Why Exponential Growth Is Dangerous
5. Logarithms: How Many Times Can I Halve?
6. Binary Search: One in a Million in 20 Steps
7. Logarithms in JavaScript
8. Compound Growth and Doubling Time
9. Recipe: The growth Module
10. Try It Yourself

1. A Function Is an Input-to-Output Machine

You already write functions. In math, a function is the same idea: a machine that takes an input and always gives back the same output for that input. Put 5 in, get 10 out; put 5 in tomorrow, get 10 out again.

function double(x) {
  return x * 2;
}

console.log(double(5)); // 10
console.log(double(0)); // 0

Mathematicians write this as f(x) = 2x, read "f of x equals 2 times x". The x is the input, and f(x) is the output. Nothing more is going on.

An input-to-output table is the quickest way to understand any function. Here is f(x) = 3x + 2:

function f(x) {
  return 3 * x + 2;
}

console.log(f(0), f(1), f(2)); // 2 5 8

Every time x grows by 1, the output grows by 3. Remember that kind of steady pattern; it is the first of three shapes you need to recognize.

Why does this matter for programmers? Because the question "how does the work grow when the data grows?" is a question about a function. The input is the size of your data (say, number of users), and the output is how much work (time, steps, memory) your code needs. The next chapter turns this into Big-O notation.

2. Three Shapes of Growth

Let n be the size of your input. Compare three simple functions:

You can print this table yourself:

for (const n of [1, 2, 3, 4, 5, 10, 100, 1000]) {
  console.log(n, n, n * n, 2 ** n);
}
// 10 10 100 1024
// 100 100 10000 1.2676506002282294e+30
// 1000 1000 1000000 1.0715086071862673e+301

(2 ** n is JavaScript's power operator, explained next, and e+30 means "times 10 to the power of 30".)

All three start at similar values, then separate:

• Linear growth: double the input, double the work. Reading every row of a file is linear.
• Quadratic growth: double the input, four times the work. Comparing every user with every other user is quadratic.
• Exponential growth: add one to the input and the work doubles. Trying every possible on/off combination of n switches is exponential.

By n = 100, the exponential column has 31 digits. No computer can finish that many steps. This is the single most important picture in the chapter.

3. Powers and Exponents

A power means repeated multiplication. In 2^5 the 2 is the base and the 5 is the exponent, and it means five 2s multiplied together:

2^5 = 2 * 2 * 2 * 2 * 2 = 32

JavaScript writes this 2 ** 5, or Math.pow(2, 5).

console.log(2 ** 10);  // 1024
console.log(2 ** 20);  // 1048576
console.log(2 ** 30);  // 1073741824
console.log(10 ** 3);  // 1000
console.log(10 ** 6);  // 1000000

Three special cases are worth memorizing:

You have seen 2^10 = 1024 before: that is the "kilo" of computing, and the reason 1 KiB is 1,024 bytes. Also notice 2 ** 32 = 4294967296 and 2 ** 31 - 1 = 2147483647; those are the integer limits from Integers, Overflow and Precision. Each extra bit doubles how many values you can store.

A handy rule: 2^a * 2^b = 2^(a + b). For example 2^3 * 2^4 = 8 * 16 = 128 = 2^7. Multiplying powers with the same base adds the exponents. That rule is the secret that makes logarithms work.

4. Why Exponential Growth Is Dangerous

Exponential growth starts slowly, which is what fools people. Three real-world pictures:

The chessboard. Put 1 grain of rice on the first square, 2 on the second, 4 on the third, doubling every square. By the 64th square the count is 2^63, about 9.2 x 10^18 grains, more rice than has ever been grown.

Folding paper. A sheet is about 0.1 millimeters thick. Each fold doubles the thickness. After 42 folds the stack is 0.1 * 2^42 mm, which is about 440,000 kilometers, farther than the Moon (about 384,000 km):

console.log((0.1 * 2 ** 42) / 1e6); // 439804.65111040004 (kilometers)

Passwords. An 8-character password using only lowercase letters has 26^8 possibilities. Adding length multiplies, so each extra character makes guessing 26 times harder:

console.log(26 ** 8);   // 208827064576      (about 208 billion)
console.log(62 ** 8);   // 218340105584896   (letters + digits, about 218 trillion)

That is why a longer password beats a "clever" short one, and why security questions with only 1,000 possible answers are useless.

In code, exponential growth shows up in recursion that calls itself twice. A famous example is Fibonacci:

function fib(n) {
  return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

console.log(fib(10)); // 55
console.log(fib(20)); // 6765
console.log(fib(30)); // 832040

It works, but each call spawns two more. fib(20) makes 21,891 calls, fib(25) makes 242,785, and fib(30) makes 2,692,537. Every +5 in the input multiplies the work by about 11. Try fib(45) and your terminal will freeze for a long time.

The practical rule: linear and quadratic code can be rescued with better hardware. Exponential code cannot. You must change the algorithm.

5. Logarithms: How Many Times Can I Halve?

The logarithm is the opposite of a power. A power asks "what do I get if I multiply 2 by itself 10 times?" and the answer is 1024. A logarithm asks the reverse: "how many times do I multiply 2 to reach 1024?" and the answer is 10.

2^10 = 1024     <=>     log2(1024) = 10

Read log2(1024) as "log base 2 of 1024". The small 2 is the base and the answer is an exponent.

Here is the friendliest way to think about it: log2(n) is roughly how many times you can cut n in half before you reach 1. Start with 1,000 items and keep halving:

1000 -> 500 -> 250 -> 125 -> 62 -> 31 -> 15 -> 7 -> 3 -> 1

That is 9 halvings, and log2(1000) is about 9.97. Close, and the difference is just rounding the fractions.

Other bases work the same way:

Because log10(n) roughly counts the digits of n, and log2(n) roughly counts the bits of n, logarithms grow incredibly slowly:

Multiplying the input by 1,000 adds only 10 to the answer. A logarithmic algorithm hardly notices how big its input is, and that is what makes logarithms so valuable to programmers.

6. Binary Search: One in a Million in 20 Steps

Here is where logarithms earn their living. Suppose I pick a secret number from 1 to 1,000,000 and you must guess it. After each guess I say "higher" or "lower".

A linear strategy (guess 1, then 2, then 3...) might take a million guesses. The smart strategy is to guess the middle every time:

• Guess 500,000. If it is "lower", you have just eliminated half of all possibilities.
• Guess 250,000, and again half of what remains disappears.
• Keep going. Each guess halves the pool.

The pool shrinks like 1,000,000 -> 500,000 -> 250,000 -> ... -> 1. How many halvings is that? 2^20 = 1,048,576, which is just above one million, so 20 guesses are enough, always. For one billion items it is only 30.

This strategy is called binary search. It requires the data to be sorted (so "higher" and "lower" mean something), like a phone book, a dictionary, or an array of sorted IDs. Here is a working version:

function binarySearch(sorted, target) {
  let low = 0;
  let high = sorted.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

const ids = Array.from({ length: 1_000_000 }, (_, i) => i * 2);
console.log(binarySearch(ids, 1999998)); // 999999
console.log(binarySearch(ids, 7));       // -1

low and high mark the part of the array still in play. Each loop looks at the middle (mid), then throws away the half that cannot contain the target. Math.floor rounds down so mid is a whole index, and the function returns -1 when the item is not found. The 1_000_000 underscores are just a readability aid for big numbers.

A plain loop would examine up to a million items; this one examines about 20. You will race the two properly in Big-O Notation.

7. Logarithms in JavaScript

JavaScript gives you three logarithm functions:

console.log(Math.log2(1024));   // 10
console.log(Math.log10(1000));  // 3
console.log(Math.log(Math.E));  // 1   (natural log, base e = 2.718...)

Math.log is the natural logarithm, base e (a special constant, about 2.71828, that appears in growth and decay). You rarely need it directly, but it gives you a way to compute a log in any base. The change of base rule says:

log_b(x) = ln(x) / ln(b)

function logBase(base, x) {
  return Math.log(x) / Math.log(base);
}

console.log(logBase(2, 1024));  // 10
console.log(logBase(5, 125));   // 3.0000000000000004
console.log(logBase(3, 81));    // 4.000000000000001
console.log(logBase(10, 1000)); // 2.9999999999999996

Look closely: the answers are almost whole numbers, not exact. This is the floating-point issue from the previous chapter showing up again. Whenever the true answer should be an integer, round it, or compare with a tolerance (nearlyEqual). When you can, prefer the dedicated Math.log2 and Math.log10.

Two more facts to keep in mind:

console.log(Math.log(0));  // -Infinity
console.log(Math.log(-1)); // NaN

You can only take the log of a positive number. And the maximum number of guesses binary search needs for n items is Math.ceil(Math.log2(n + 1)):

console.log(Math.ceil(Math.log2(1_000_000 + 1))); // 20
console.log(Math.ceil(Math.log2(1000 + 1)));      // 10

The Math.ceil rounds up because a fraction of a guess still costs a whole guess.

8. Compound Growth and Doubling Time

Exponential growth is not only a danger; it is also how money grows. Suppose you put $1,000 in a savings account that pays 7% per year. Each year the balance is multiplied by 1.07 (the original plus 7%). After y years:

balance = principal * (1 + rate) ^ years

This is compound growth, since each year's interest earns interest too. In JavaScript:

function compound(principal, ratePercent, years) {
  return principal * (1 + ratePercent / 100) ** years;
}

for (const y of [0, 5, 10, 20, 30]) {
  console.log(y, compound(1000, 7, y).toFixed(2));
}
// 0 1000.00
// 5 1402.55
// 10 1967.15
// 20 3869.68
// 30 7612.26

The first 10 years add about $967, and the last 10 add about $3,743. Same rate, but bigger base: the curve bends upward. It is the same picture as the 2^n column, just with a gentler base of 1.07.

Now the question "how long until my money doubles?" is a logarithm: how many multiplications by 1.07 reach 2? The answer is log(2) / log(1.07):

function doublingTime(ratePercent) {
  return Math.log(2) / Math.log(1 + ratePercent / 100);
}

console.log(doublingTime(7).toFixed(2));  // 10.24
console.log(doublingTime(1).toFixed(2));  // 69.66
console.log(doublingTime(10).toFixed(2)); // 7.27

At 7% your money doubles in about 10.2 years. People use the rule of 72 as a mental shortcut: divide 72 by the rate. 72 / 7 is about 10.3, very close to the real answer.

The same math describes things that grow in your systems: a service whose traffic grows 5% every week doubles in about 14 weeks, a database that grows 10% per month doubles in about 7 months. Doubling-time thinking helps you answer "when will we run out of disk or capacity?" before it becomes an emergency.

And it works backward. Debt at a high interest rate, or a viral bug that doubles error reports every hour, is exponential growth you do not want.

9. Recipe: The growth Module

Add this chapter's tools to mathlab. Create src/growth.js:

// src/growth.js

// Worst-case number of guesses binary search needs for n sorted items.
export function stepsToBinarySearch(n) {
  return Math.ceil(Math.log2(n + 1));
}

// Logarithm of x in any base (may be off by a tiny float error).
export function logBase(base, x) {
  return Math.log(x) / Math.log(base);
}

// Years (or periods) for something growing at ratePercent to double.
export function doublingTime(ratePercent) {
  return Math.log(2) / Math.log(1 + ratePercent / 100);
}

// Value after compounding principal at ratePercent for a number of years.
export function compound(principal, ratePercent, years) {
  return principal * (1 + ratePercent / 100) ** years;
}

Re-export it from src/index.js:

export * from "./growth.js";

Add this to demo.js and run node demo.js:

import {
  stepsToBinarySearch, logBase, doublingTime, compound,
} from "./src/growth.js";

console.log("--- growth ---");
console.log(stepsToBinarySearch(1000));          // 10
console.log(stepsToBinarySearch(1_000_000));     // 20
console.log(stepsToBinarySearch(1_000_000_000)); // 30
console.log(logBase(2, 1024));                   // 10
console.log(logBase(3, 81));                     // 4.000000000000001
console.log(doublingTime(7).toFixed(2));         // 10.24
console.log(compound(1000, 7, 10).toFixed(2));   // 1967.15

Notice logBase(3, 81) is not exactly 4. That is expected, and a good reminder to round before showing a result to a user.

10. Try It Yourself

1. Build a growth table. Write a loop for n from 1 to 10 that prints n, n * n, n ** 3, and 2 ** n on one line. At what n does 2 ** n first beat n ** 3? (Check your answer against the output.)
2. Count the halvings. Write halvings(n) that repeats n = Math.floor(n / 2) until n is 1, counting the steps. Test it with 1024 and 1000000. Compare with Math.log2(n). Why does 1000000 give 19 here but binary search needs 20 guesses?
3. Folding challenge. How many folds of a 0.1 mm sheet are needed to exceed the height of Angkor Wat (about 65 meters)? Use a loop, then confirm with Math.ceil(Math.log2(65 / 0.0001)).
4. Password strength. Write passwordSpace(alphabetSize, length) using **. Compare 8 lowercase letters (26), 8 mixed-case letters and digits (62), and 12 lowercase letters. Which is bigger?
5. When do we run out? A disk has 500 GB free and your data grows 8% per month and currently uses 100 GB. Using compound, find the first month the data exceeds 500 GB. (Hint: loop the months, or compute Math.log(5) / Math.log(1.08).)
6. Break fib. Time fib(30) and fib(35) with console.time. By roughly how much does the time increase? What does that suggest about fib(50)?

Next, we'll give this growth vocabulary a name that every programmer uses, and learn to read nested loops at a glance, in Big-O Notation.