Chapter 4: Performance

Question 1

5-step approach to the scientific method

Answer 1

• Observe some feature of the natural world
• Hypothesize a model that is consistent with the observations
• Predict events using the hypotheses
• Verify the predictions by making further observations
• Validate by repeating until the hypothesis and observations agree

Question 2

Empirical analysis

Answer 2

A method whereby one develops a doubling hypothesis to double the size of the input and observe the effect on the running time.

Question 3

2 Primary factors determining running time (Knuth)

Answer 3

• Cost of executing each statement

- The frequency of execution of each statement

Question 4

Constant order of growth program

Answer 4

A program that executes a fixed number of statements to finish its job; consequently its running time does not depend on the problem size.

Question 5

Linear order of growth program

Answer 5

A program whose running time is directly proportional to the problem size.
Ex.
Programs that spend a constant amount of time processing each piece of input data, or that are based on a single for loop.

Question 6

Linearithmic order of growth program

Answer 6

A program whose running time for a problem of size N has order of growth N log N.

Question 7

Quadratic order of growth program

Answer 7

N^2 order of growth
Ex.
Two nested for loops, used for some calculation involving all pairs of N elements.

Question 8

Cubic order of growth program

Answer 8

N^3 order of growth
Ex.
Three nested for loops (Running time of matrix multiplication).

Question 9

Exponential algorithm

Answer 9

Algorithm whose order of growth is b^N for any constant b>1