**Tom Kelliher, CS23**

**Apr. 12, 1996**

Algorithm analysis covers:

- Running time (worst, average case)
- Correctness

What determines running time?

- Hardware.
- The input.
- Software (system and user).

How is it fair to compare two programs?

Should we compare?

What should we compare?

Why should we compare?

Idea: count something.

Examples:

- Sorting employee records.
- Searching employee records.
- Finding a path in a graph.
- Eight queens problem.

How many times does the inner loop body execute?

for (i = 0; i < n; ++i) for (j = 0; j < i; ++j) ; // inner loop body

Find closed forms for:

- Constant.
- Logarithmic.
- Linear.
- Polynomial.
- Exponential.

Definition:

if constants **c** and exist such that for all .

Consequences:

- Ignore low order terms.
- Ignore multiplicative constants.
- Big Oh is distributive.

Examples:

A fallacious example: is O.

Typical growth rates (from slowest to fastest)

Worst-case analysis.

Average-case analysis.

Why use a difficult, subtle, fast algorithm on small inputs?

What is the efficiency of

- Bubble sort.
- Merge sort.
- Linear search.
- Binary search.

Implement mergesort (don't look in the textbook!).

Thu Apr 11 16:04:24 EDT 1996