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