Algorithm Analysis

Tom Kelliher, CS23

Apr. 12, 1996

Algorithm analysis covers:

What determines running time?

How is it fair to compare two programs?

Should we compare?

What should we compare?

Why should we compare?

Execution Time

Idea: count something.

Examples:

Counting

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:

Growth Rates

The Order of an Algorithm

Definition:

if constants c and exist such that for all .

Consequences:

Examples:

A fallacious example: is O.

Typical growth rates (from slowest to fastest)

Worst-case analysis.

Average-case analysis.

Perspective

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

Application

What is the efficiency of

Exercise

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



Thomas P. Kelliher
Thu Apr 11 16:04:24 EDT 1996
Tom Kelliher