Algorithm Analysis

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?

Execution Time

Idea: count something.

Examples:

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

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

• Constant.
• Logarithmic.
• Linear.
• Polynomial.
• Exponential.

The Order of an Algorithm

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.

Perspective

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

Application

What is the efficiency of

• Bubble sort.
• Merge sort.
• Linear search.
• Binary search.

Exercise

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