# 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