Foundations
Logarithms & Exponentiation
Difficulty: Beginner
How can a search through a million sorted items finish in roughly twenty comparisons? The answer is log2(n), and once you internalize what that expression really means, an entire family of fast algorithms (binary search, balanced trees,...
Logarithms & Exponentiation
How can a search through a million sorted items finish in roughly twenty comparisons? The answer is log_2(n), and once you internalize what that expression really means, an entire family of fast algorithms (binary search, balanced trees, divide-and-conquer) suddenly stops feeling like magic.
Logarithms & Exponentiation builds your intuition for the math behind O(log n). You will start from a concrete framing (a logarithm answers the question "how many times can I halve n before reaching 1?") and work through the powers-of-2 sequence (1, 2, 4, 8, 16, ...) that appears constantly in computer science. You will pick up the three logarithm properties you actually need (log(a * b) = log(a) + log(b), log(a^n) = n * log(a), and log(1) = 0), see why the base does not matter inside Big-O, meet fast exponentiation as a preview of O(log n) in action, and trace why every halving loop produces logarithmic complexity.
In Big-O Notation (Upper Bound), you learned that O(log n) sits between O(1) and O(n) in the hierarchy and is associated with algorithms that halve their work each step. This lesson supplies the mathematical reason that pattern produces a logarithm, so the complexity class stops being something you memorize and starts being something you can derive.
Once logarithms feel comfortable, you will be ready for Mathematical Sequences, where you will study arithmetic sums, geometric series, and Fibonacci patterns that explain the running times of everything from nested loops to recursive algorithms.
Prerequisites:
Big-O Notation (Upper Bound)Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain what a logarithm is using the 'how many times can you halve?' intuition.
Compute simple log base 2 values mentally using powers of 2.
Apply the three key logarithm properties: product, power, and identity rules.
Recognize the powers-of-2 sequence and its role in CS.
Explain why binary search and similar halving algorithms are O(log n).
Why This Matters
01
O(log n) is one of the most common complexity classes, and you cannot understand it without understanding logarithms.
02
Powers of 2 are the foundation of binary representations, tree heights, and divide-and-conquer algorithms.
03
Interviewers expect you to explain why binary search is O(log n) and what that means for large inputs.
Key Terms
6 terms you'll encounter in this lesson
Logarithm
The inverse of exponentiation. log_b(x) asks: 'To what power must I raise b to get x?'
log base 2 (log2)
The most common logarithm in CS. log2(n) equals the number of times you can halve n before reaching 1.
Exponentiation
Repeated multiplication. b^n means multiplying b by itself n times.
Powers of 2
The sequence 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ... Each value is 2^k for k = 0, 1, 2, ...
O(log n)
A complexity class where the work grows by a fixed amount each time the input size doubles. Extremely efficient.
Fast exponentiation
A technique to compute b^n in O(log n) multiplications by repeatedly squaring, instead of O(n) multiplications.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"log n means the algorithm runs n times"
log n is much smaller than n. log2(1,000,000) is only about 20. An O(log n) algorithm on a million elements does roughly 20 operations, not a million.
"The base of the logarithm matters in Big-O"
In Big-O, the base does not matter because log_a(n) = log_b(n) / log_b(a), and 1/log_b(a) is a constant. So O(log2 n) = O(log10 n) = O(ln n) = O(log n).
"log(0) and log(negative) are fine"
Logarithms are only defined for positive numbers. log(0) is undefined, and log of a negative number is undefined in real numbers.