**Tom Kelliher, CS23**

**Apr. 21, 1996**

Algorithm analysis covers:

- Running time (worst, average case)
- Correctness

What determines running time?

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

Questions:

- How is it fair to compare two programs?
- Should we compare?
- What should we compare?
- Why should we compare?

- Can we measure time?
- What do we measure?
- Measure as a function of what?
- Idea: count something.

What should we count?

- 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. (Familiarity with properties of logarithms?)
- 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.

Another: 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 merge sort (don't look in the textbook!).

Sat Apr 19 13:42:29 EDT 1997