Lecture Notes for CS 512, Algorithm Design

30 September 1999

1. how to characterize an algorithm's behavior?

2. how to compare two algorithms?

3. measure them

   1. good - definitive

   2. bad - extra work, non-portable, detailed, requires implementation, compaisons hard

4. need a more abstract estimator

   1. asymptotic or big-oh notation

   2. presents approximate behavior, ignoring details - constants represent details

   3. behaviors as functions of input size, other details abstracted away.

   4. examine what happens as n grows large, that is, approaches infinity asymptotically

   5. input usually characterized as worst case - best case too unrealistic and average case usually too difficult to characterize.

5. order notation

   1. big omicron

      1. characterizes an upper bound

      2. g is O(f) if there exists constants c and N such that for all n > N, g(n) <= cf(n)

      3. because constants don't matter, use simplest functions; O(n), not O(2n)

      4. monotonic functions; exponentials grow faster than polynomials; n grows faster than log n

      5. addition and multiplication of functions

      6. tight and loose (upper) bounds

   2. big omega

      1. characterizes the - not a - lower bound

      2. g is O(f) if there exists constants c and N such that for all n > N, g(n) => cf(n)

      3. lower bounds are hard, because they range over all solutions

   3. big theta

      1. tight bounds

      2. f(n) bounded above and below by g(n)

   4. little omicron and omega

      1. strict bounds, non-tight bounds

   5. keep your eye on the constants

6. time and space complexity

This page last modified on 13 October 1999.