Base 2 logarithms come up everywhere in this class (and CS).
Some characterizations of
:
- The number of times we can divide n by 2 before we get 1 or
less.
- The number of bits in the binary representation of n.
- A way to turn multiplication into addition:
. - The inverse function of 2n.
The function
grows much more slowly than n or 1/100
n or even
.
The book lists a bunch of amazing properties of this function.
I'll introduce them as needed.
Next: Iteration Count for Russian
Up: ANALYZING RUSSIAN
Previous: Counting Iterations