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