Java Reference
In-Depth Information
Example2.5
For the powerset of the integers, the subset operator defines
a partial order (because it is antisymmetric and transitive). For example,
f1; 2gf1; 2; 3g. However, sets f1; 2g and f1; 3g are not comparable by
the subset operator, because neither is a subset of the other. Therefore, the
subset operator does not define a total order on the powerset of the integers.
2.2
Miscellaneous Notation
Units of measure: I use the following notation for units of measure. “B” will
be used as an abbreviation for bytes, “b” for bits, “KB” for kilobytes (2
10
=
1024 bytes), “MB” for megabytes (2
20
bytes), “GB” for gigabytes (2
30
bytes), and
“ms” for milliseconds (a millisecond is
1
1000
of a second). Spaces are not placed be-
tween the number and the unit abbreviation when a power of two is intended. Thus
a disk drive of size 25 gigabytes (where a gigabyte is intended as 2
30
bytes) will be
written as “25GB.” Spaces are used when a decimal value is intended. An amount
of 2000 bits would therefore be written “2 Kb” while “2Kb” represents 2048 bits.
2000 milliseconds is written as 2000 ms. Note that in this topic large amounts of
storage are nearly always measured in powers of two and times in powers of ten.
Factorial function: The factorial function, written n! for n an integer greater
than 0, is the product of the integers between 1 and n, inclusive. Thus, 5! =
1 2 3 4 5 = 120. As a special case, 0! = 1. The factorial function grows
quickly as n becomes larger. Because computing the factorial function directly
is a time-consuming process, it can be useful to have an equatio
n tha
t provides a
good approximation. Stirling's approximation states that n!
p
2n(
e
)
n
, where
e 2:71828 (e is the base for the system
of na
tural logarithms).
3
Thus we see that
p
2n=e
n
< 1), it grows faster than c
n
for
while n! grows slower than n
n
(because
any positive integer constant c.
Permutations: A permutation of a sequence S is simply the members of S ar-
ranged in some order. For example, a permutation of the integers 1 through n
would be those values arranged in some order. If the sequence contains n distinct
members, then there are n! different permutations for the sequence. This is because
there are n choices for the first member in the permutation; for each choice of first
member there are n 1 choices for the second member, and so on. Sometimes
one would like to obtain a random permutation for a sequence, that is, one of the
n! possible permutations is selected in such a way that each permutation has equal
probability of being selected. A simple Java function for generating a random per-
mutation is as follows. Here, the n values of the sequence are stored in positions 0
3
The symbol “” means “approximately equal.”
