1.3 MATHEMATICAL BACKGROUND 15These properties can be combined to help simplify a function. Equation 1.7 is
a good fact to know for base conversion. Most calculators do log 10 and natural
logs, but let’s say you need to know log 42 75. Equation 1.7 would help you
find the answer of 1.155.
■ 1.3.2 Binary Trees
A binary tree is a structure in which each node in the tree is said to have at
most two nodes as its children, and each node has exactly one parent node.
The top node in the tree is the only one without a parent node and is called
the root of the tree. A binary tree that has N nodes has at least lgN + 1 lev-
els to the tree if the nodes are packed as tightly as possible. For example, a full
binary tree with 15 nodes has one root, two nodes on the second level, four
nodes on the third level, eight nodes on the fourth level, and our equation
gives lg 15 + 1 = 3.9 + 1 = 4. Notice, if we add one more node to this
tree, it has to start a new level and now lg 16 + 1 = 4 + 1 = 5. The largest
binary tree that has N nodes will have N levels if each node has exactly one
child (in which case the tree is actually a list).
If we number the levels of the tree, considering the root to be on level 1,
there are 2K–1 nodes on level K. A complete binary tree with J levels (num-
bered from 1 to J) is one where all of the leaves in the tree are on level J, and all
nodes on levels 1 to J 1 have exactly two children. A complete binary tree
withJ levels has 2J 1 nodes. This information will be useful in a number of
the analyses we will do. To better understand these formulas, you might want
to draw some binary trees and compare your count of the nodes with the
results of these formulas.
■ 1.3.3 Probabilities
Because we will analyze algorithms relative to their input, we may at times
need to consider the likelihood of a certain set of input. This means that we
will need to work with the probability that the input will meet some condi-
tion. The probability that something will occur is given as a number in the
range of 0 to 1, where 0 means it will never occur and 1 means it will always
occur. If we know that there are exactly 10 different possible inputs, we can
say that the probability of each of these is between 0 and 1 and that the total of
all of the individual probabilities is 1, because one of these must happen. If
there is an equal chance that any of these can occur, each will have a probabil-
ity of 0.1 (one out of 10, or 1/10).