Lecture Notes for CS 512, Algorithm Design

Algorithm Analysis, 13 March 2000

  1. going from algorithm to order notation - many ways

    1. algorithm, mathematical model (that is, function), order approximation - knuth

      1. subsidiary model - computation model; ram, mix

    2. algorithm, order notation - structural analysis

  2. structural analysis - algorithm structure

    1. assign behavior to smaller units, then combine units following algorithm structure to find behavior of larger units.

    2. statements

      1. usually O(1), but know your data structures - eg a[i] vs. put_queue(q, i) vs. put_priority_queue(q, i)

    3. statement sequence - s1 ; s2

      1. s1 is O(f), s2 is O(g), so s1; s2 is O(f) + O(g)

      2. but what is O(f) + O(g)

        1. treat O(f) as a set of functions, pick a representative function and apply the definition of big-oh.

        2. plus, max, constant

        3. example: i <- 1 ; heapify(h, i)

    4. loops - do b s od

      1. s gets executed some number of times - asymptotically bound the number of times

      2. O(f)*O(g) - what is that

      3. implicit, and occasionally troublesome, assumption - the loop itself does constant work per iteration.

    5. if statement - if b1 s1 or b2 s2 fi

      1. execute either s1 or s2 - which one

      2. don't forget b1 and b2

    6. what about subroutine calls and recursion

      1. factorial

      2. remember - a mathematical function for resource use

      3. recurrence relations

  3. fine points

    1. what is the input - what's n

    2. making the assumptions - best, average, worst

    3. what's the output - what are we measuring; memory accesses, comparisons, swaps and so on

This page last modified on 21 March 2000.