cs230 Lecture Notes
Spring 2002
Week 13 Monday

Today's topics
--------------

1) Hashtable implementation

2) Hashtable performance analysis (notes22.txt)

3) Performance analysis


Performance analysis reprise
----------------------------

We want to compare algorithms, but there are some problems:

1) relative performance might depend on hardware issues

   Solution: count abstract operations

2) relative performance might depend on the details of the problem

   Solution: compare worst case behavior

             (or sometimes average case; seldom best case)

3) relative performance depends on problem size

   Solution: express run time as a function of problem size
             and then compare the asymptotic behavior of the
	     functions

The what now?

What we have been calling order of growth is also called
asymptotic behavior because it describes the behavior of
the function as (usually) n goes to infinity.


A complexity class is the set of all functions with the
same asymptotic behavior.

All the linear functions belong to the set O(n),
pronounced "Big-Oh of n"

Strictly, to say that  f(n) belongs to O(g(n)) is to
say that there are values c and n* such that

    f(n) < c g(n)              for all n > n*

In other words, for large n, f is bounded by some
multiple of g.

To see why this is meaningful, consider why n^2 is not in O(n).















Also, notice that the constant c is arbitrary, which is why,
when classifying algorithms, we ignore leading constants.


Properties of combination
-------------------------

If f(n) is O(g(n)), what can we say about  k f(n)?

If f1(n) and f2(n) are O(g(n)), what can we say about  f1(n) + f2(n)?

If  f1(n) is O(g(n)), 
and f2(n) is O(h(n)),
what can we say about  f1(n) + f2(n)?

If  f1(n) is O(g(n)), 
and f2(n) is O(h(n)),
what can we say about  f1(n) * f2(n)?

Examples:  What is the order of growth of

1) n^3 + n^2

2) n^3 + 1000000000000000000000000000000000000000000 n^2

3) (n^2 + n) * (n + 1)