1.3. THINGS USEFUL TO KNOW
13
1.3.4
Secondary Storage
It is important, when dealing with large-scale data, that we have a good un-
derstanding of the diﬀerence in time taken to perform computations when the
data is initially on disk, as opposed to the time needed if the data is initially in
main memory. The physical characteristics of disks is another subject on which
we could say much, but shall say only a little and leave the interested reader to
follow the bibliographic notes.
Disks are organized into blocks, which are the minimum units that the oper-
ating system uses to move data between main memory and disk. For example,
the Windows operating system uses blocks of 64K bytes (i.e., 216 = 65,536 bytes
to be exact). It takes approximately ten milliseconds to access (move the disk
head to the track of the block and wait for the block to rotate under the head)
and read a disk block. That delay is at least ﬁve orders of magnitude (a factor
of 105) slower than the time taken to read a word from main memory, so if all
we want to do is access a few bytes, there is an overwhelming beneﬁt to having
data in main memory. In fact, if we want to do something simple to every byte
of a disk block, e.g., treat the block as a bucket of a hash table and search for
a particular value of the hash-key among all the records in that bucket, then
the time taken to move the block from disk to main memory will be far larger
than the time taken to do the computation.
By organizing our data so that related data is on a single cylinder (the
collection of blocks reachable at a ﬁxed radius from the center of the disk, and
therefore accessible without moving the disk head), we can read all the blocks
on the cylinder into main memory in considerably less than 10 milliseconds
per block. You can assume that a disk cannot transfer data to main memory
at more than a hundred million bytes per second, no matter how that data is
organized. That is not a problem when your dataset is a megabyte. But a
dataset of a hundred gigabytes or a terabyte presents problems just accessing
it, let alone doing anything useful with it.
1.3.5
The Base of Natural Logarithms
The constant e = 2.7182818 · · · has a number of useful special properties. In
particular, e is the limit of (1 + 1
x)x as x goes to inﬁnity. The values of this
expression for x = 1, 2, 3, 4 are approximately 2, 2.25, 2.37, 2.44, so you should
ﬁnd it easy to believe that the limit of this series is around 2.72.
Some algebra lets us obtain approximations to many seemingly complex
expressions. Consider (1 + a)b, where a is small. We can rewrite the expression
as (1+a)(1/a)(ab). Then substitute a = 1/x and 1/a = x, so we have (1+ 1
x)x(ab),
which is
1 + 1
x
xab
Since a is assumed small, x is large, so the subexpression (1 + 1
x)x will be close
to the limiting value of e. We can thus approximate (1 + a)b, for small a, as
eab.
