Exercise: Analysis of Sequential Search

Basic Operation: number of key comparisons

• Best case:
• Worst case:
• Average case:

Finding the average case:
Specify the distribution to average over (do we assume that the item is in the collection? 50% likely to be in the collection? In this case we will assume the key is in the array, and equally likely to be at any position.)

Sum over the cost of all possible outcomes, and divide by the number of outcomes.

Average Case Analysis

Basic Operation: number of key comparisons

• Best case: comparison
• Worst case: comparisons
• Average case:

Finding the average case:
Specify the distribution to average over (do we assume that the item is in the collection? 50% likely to be in the collection? In this case we will assume the key is in the array, and equally likely to be at any position.)

Sum over the cost of all possible outcomes, and divide by the number of outcomes.

Formal Definition of Big-O

For a non-negative function, if and only if there exist positive constants and such that for all .

Formal Definition of Big-O

• Informal rule of "dropping constants" follows immediately:
  • Yes! choose c = 50, = 1, clearly
  • for all

Formal Definition of Big-O

• Informal rule of ``dropping lower-order terms'' also follows:
  • Notice that:
  • Choose c = 41, = 1, clearly
    for all

Big-O Describes and Upper-Bound

• Big O is loosely analogous to
• All of these statements are true:
  
  
  
  

Upper Bounds

• Big-O descriptions are imprecise in two different ways:
  • No constants or lower-order terms
    • GOOD: fewer distractions
  • Only provides an upper bound. Correct to say an algorithm requires steps, even if it only requires steps.
    • UNFORTUNATE: conveys an incomplete analysis

Big Omega

For a non-negative function, if and only if there exist positive constants and such that for all .

• Big is loosely analogous to
• All of these statements are true:
  
  
  
  (Note: We would never write this!)

Big Theta

• Big is loosely analogous to
• Which of these statements are true?
  
  
  
  
  

Uses of Big-O in the Wild

In practice, people use big-O in several different ways:

• We might say: "The best algorithm for the traveling salesperson problem is in ."
  • Because: no one knows exactly how fast the fastest algorithm is. We can only bound it from above.
  • This is an approved OpenDSA usage.
• We might say: "Sequential search requires steps."
  • Because: is the upper bound across possible inputs. It could actually be lower if we happen to find the key at the beginning of the array.
  • Our textbook discourages this use. Better to say that the run time is in the worst case.
• People might say "The worst case for sequential search is ".
  • This is a sloppy way of speaking, but it is understandable given that we generally give the tightest possible bound.

Socrative Quiz

Alyce is working on the analysis of a complex algorithm for finding sequence matches in a DNA database. She can easily show that the algorithm requires no more than base-pair comparisons in the worst case. She hopes to show that the algorithm requires at most comparisons. How should Alyce describe the running time of the algorithm given the current state of her analysis?

A)
B)
C)
D)
E)

Socrative Quiz

What relationship(s) is(are) illustrated by the following figure?

A) B) C) D) E) F) G) A, B and C are all correct H) D, E and F are all correct