## Analyzing Algorithms

# Analyzing Algorithms

**Bart Massey**

### Two dimensions:

Correctness (tomorrow)

Performance (today)

### Performance of Algorithms:

Algorithms run on instances

Performance varies with instance size, "difficulty"

- Key performance measures: time, space (memory/storage)
- "big-O" notation family captures gross change with size

Difficulty of problem is worst-case difficulty of instances

Difficulty of instance is performance of best-possible-performing algorithm

### Review: The big-O notation family

f(n) in O(g(n)) == exists c, n0 . forall n > n0 . 0 <= f(n) <= c * g(n)

Example:

```
7*n^2+n+1 in O(n^2) because
7*n^2+n+1 <= 7*n^2 + n^2 + 1 = 8*n^2 + 1
```

Similarly Omega, Theta, little-O

Note the restictions, in particular "for sufficiently large n"

Common classes: O(1), O(lg n), O(n), O(n lg n), O(n^2), O(n^k), O(2^n), O(n^n)

### What is "n"?

Best is measure of instance size (or info content)

Example: multiplication

- O(1): "numbers are atomic and CPUs multiply"
- O(|n|^2) = O((lg n)^2): "numbers are in binary, multiplication uses constant-time additions, grade-school algorithm"
- O(n*|n|) = O(n lg n): "numbers are in binary, repeated-addition algorithm"

### Analyzing sorting

```
SEQUENCE SORTING
Instance: A sequence s of elements drawn from a set S. A
total order q: SxS->B s.t. q is true when its
arguments are "in order".
Problem: Find a sequence t drawn from S s.t.
t in perm(s) and
forall i, j in 1..|S| . i < j => q (t[i], t[j])
ALGORITHM DUMBSORT
To sort s:
for each permutation t of s
if t satisifies the definition of sorted
return t
ALGORITHM SELECTION SORT
To sort s:
t <- empty
while s is not empty
let i be the index of a minimum element of s
append s[i] to t
delete s[i] from s
```

Last modified: Tuesday, 15 April 2014, 3:44 PM