uccser/cs-field-guide

# Logarithm

Logarithm is a very slow growing mathematical function written as \( log n \).
In computer science logarithms are usually in base 2, that is, \( log_2 n \), which is the inverse of the incredibly fast growing exponent function \( 2^n \).
Logarithms are not needed to understand the material in this book, but they are used a lot in computer science and are a useful concept to understand.
Logarithms happen to come up a lot with algorithms, and the two words are often confused.
The value \( log_2 n \) is just the number of times you can halve n until you get down to 1; for example, \( \log_2 32 \) is 5, and \( log_2 1024 \) is 10.
Binary search takes \( log_2 n \) steps to search n items; storing the number n in binary takes \( log_2 n \) bits.