# 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:

• 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!).

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