Chapter 3. Runtime Analysis.

1. Program complexity factors: time, space, programmer effort.

2. Program analysis strategies:
a. Measure real values.
Must measure output for all categories of input.
Measures depend on hardware/software platform.
Have to implement code to be able to do this.

b. Estimate values based on past experiences.
Hard to do accurately.
Usually done to some extent, however.

c. Construct mathematical model of time, space or effort, and then solve the equations.
The more complex the algorithm or problem is, the harder it is to model correctly and solve.
If make simplifying assumptions, the models can be less complex.
The simplified models can be very useful for determining upper and lower bounds.

3. Examples code segments for counting number of steps:
TofN.java
RuntimeDriver.java

4. Definition of big-Oh: section 3.4.1, pp. 118 in text.
a. Examples of f(n) and g(n) functions, and c and n0 values, to demonstrate definition of big-Oh.
b. In-class-exercise on determining the runtime equation and big-oh equivalents for a set of methods.
c. Asymptotic Analysis: section 3.4.2.