cs230 Lecture Notes
Week 2, Tuesday

For today you should have finished Homework 0 and read Chapter 3.

For Thursday you should read Chapters 4 and 5.

In lab you will start Homework 1, which is due next Tuesday.


Quiz 1


Searching
---------

Quiz 1 solution.  Linear search.


Quiz 1 solution.  Bisection search.



Performance analysis part one
-----------------------------

How long does it take to do a linear search?

In the best case, we only have to look at one element.

In the worst case, we have to look at all n elements.

Average case?  Well, if we assume the first location is
equally likely to be anywhere, then on average we have
to look at n/2 elements.



How long does it take to do a bisection search?

At each recursive step, the number of elements in the
array is roughly halved.

Starting with n, how many halvings does it take before
you get to 1.

Starting with 1, how many doublings does it take to
get to n?

2 raised to what power is n?


Which is bigger, n/2 or log2 n?