SUNY Geneseo Department of Computer Science

Execution Time of Binary Search

{Date}

CSci 141, Spring 2004
Prof. Doug Baldwin

Return to List of Lectures

Previous Lecture

Misc

Hand out Homework 2

Questions?

Binary Search

    boolean search( A, x, low, high )
        if ( low <= high )
            mid = (low + high) / 2
            if ( A[mid] < x )
                return search( A, x, mid+1, high )
            else if ( A[mid] > x )
                return search( A, x, low, mid-1 )
            else
                return true
        else
            return false

Efficiency

How to express efficiency - Section 9.2.2

Theoretical operations might or might not relate to execution time
- e.g., n² grows faster than n terms
Asymptotic notation = taking fastest-growing term of expression

[Functions that Do or Don't Grow Proportionally to b(n)]

Comparing these fastest-growing terms is often best
- Works best for high n values
Beware of "=" in asymptotic notation
- e.g., n² + n = Theta(n²)
How to prove asymptotic notation correct (optional material for this course)
- Get values for c2, n2 to make other equation hold
- Not just one value that makes this true
- Any value is OK
Experimental test for asymptotic equivalence:
- Look for rough constant of proportionality

Best case: find x in middle of section

How many steps is this?
- 1: "low <= high"
- or 4: "low <=high", "mid =...", "A[mid] <..." , "A[mid] > ..."
- etc.
Theta(1)

Worst case

Count "low <= high" comparisons
C(n) = # of these comparisons, in worst case, for array of n elements
- C(n) = 1 if n = 0
- C(n) = 1 + C( (n-1)/2 ) if n > 0

[Remove One of n Elements (Middle), Divide Remaining n-1 in Half]

Maybe Theta(n/2)
- Or sqrt(n) + 2
But (n-1)/2 isn't always an integer
- Restrict n just to values for which (n-1)/2 is integer

[Closed Form Can Sample True Function]

C(0 = 2⁰-1) = 1
C(1 = 2¹-1) = 1 + C( (1-1)/2 ) = 1 + 1
C(3 = 2²-1) = 1 + C( (3-1)/2 ) = 1 + C(1) = 1 + 1 + 1
C(7 = 2³-1) = 1 + C(3) = 1 + 1 + 1 + 1

Maybe C(n) is the opposite of 2ⁿ, i.e., log₂(n)
- What about log₂(n+1)?
- Looks like C(n) = log₂(n+1) + 1
- Exercise for the listener to prove this
log₂(n+1) + 1 = Theta( log(n) )

Introduction to lists

Read Section 11.1 through Section 11.3.1

Next Lecture