Java Reference
In-Depth Information
We can use a similar process to prove many recursive programs correct. The
general form is to show that the base cases perform correctly, and then to use the
induction hypothesis to show that the recursive step also produces the correct result.
Prior to this, we must prove that the function always terminates, which might also
be done using an induction proof.
2.7
Estimation
One of the most useful life skills that you can gain from your computer science
training is the ability to perform quick estimates. This is sometimes known as “back
of the napkin” or “back of the envelope” calculation. Both nicknames suggest
that only a rough estimate is produced. Estimation techniques are a standard part
of engineering curricula but are often neglected in computer science. Estimation
is no substitute for rigorous, detailed analysis of a problem, but it can serve to
indicate when a rigorous analysis is warranted: If the initial estimate indicates that
the solution is unworkable, then further analysis is probably unnecessary.
Estimation can be formalized by the following three-step process:
1. Determine the major parameters that affect the problem.
2. Derive an equation that relates the parameters to the problem.
3. Select values for the parameters, and apply the equation to yield an estimated
solution.
When doing estimations, a good way to reassure yourself that the estimate is
reasonable is to do it in two different ways. In general, if you want to know what
comes out of a system, you can either try to estimate that directly, or you can
estimate what goes into the system (assuming that what goes in must later come
out). If both approaches (independently) give similar answers, then this should
build confidence in the estimate.
When calculating, be sure that your units match. For example, do not add feet
and pounds. Verify that the result is in the correct units. Always keep in mind that
the output of a calculation is only as good as its input. The more uncertain your
valuation for the input parameters in Step 3, the more uncertain the output value.
However, back of the envelope calculations are often meant only to get an answer
within an order of magnitude, or perhaps within a factor of two. Before doing an
estimate, you should decide on acceptable error bounds, such as within 25%, within
a factor of two, and so forth. Once you are confident that an estimate falls within
your error bounds, leave it alone! Do not try to get a more precise estimate than
necessary for your purpose.
Example2.18
How many library bookcases does it take to store topics
containing one million pages?
I estimate that a 500-page book requires
