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)
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)
- 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"
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