COSC 350: Data Structures
Feb. 11, 2009

Analysis of Algorithms

Performance perspective vs error checking, readability, adaptability & code reuse

Efficency problems:
1. Ignoring,
2. Obsessing (hand coding vs compiler optimizations)

Assumes correctness

Why analyze performance?
1. Compare algorithms, 2. Predict performance, especially with new environment (computer) or larger data set, 3. set parameters

Three Approaches:
1. Look it up
2. Emperically measure
3. Mathematical analysis

Emperical

1. Need actual (correct & complete) implementation
2. Select Data: actual, random, perverse
(best, average, worst—best if average = worst)

Mathematical

1. Identify abstract operations
Tricky! Consider: simple assignment vs record assignment, comparing numbers vs. records
2. Size of problem
One or more parameters (M x N in 1st Union Find)

Types of Complexity (p37 in text)

Code Examples

Growth: Table from Gary & Johnson (p7)

Dropping terms, what's important

Big-O: Upper bound
Big-Omega: Lower bound
Big-Theta: Tight bound

Homework:

This page was created by Joe Sloan.
It was last modified around: 11 February 2009
Send mail to: sloanjd@wofford.edu