# 161 Midterm 1

The flashcards below were created by user CMortty on FreezingBlue Flashcards.

1. Sequential Search of an Ordered List
• WC:
• AVG (x in list):
• AVG (x not in list):
• AVG (50% in 50% not):
2. Binary Search of an Ordered List
• WC:
• AVG (x in list):  where
• AVG (x not in list):  where
3. Interpolation Search
• Works well with data in order and uniformly distributed
• Like looking in a phone book
• WC:
• AVG:
4. Straight Insertion Sort
• WC C:
• AVG C:
• M:
• T:
• S:
5. Binary Insertion Sort
• WC C:
• AVG C:
• M:
• T:
• S:
6. Heapsort
• C:
• M:
• S:
• T:
7. Bucket Sort
• T:
• S:
• T:
• S:
• M is the base
9. Shellsort
• Uses tables to sort
• Video showed decreasing tables over time to the items next to each other
• Use straight insertion to sort each table
10. Definition of Upper Bound (O notation)
if  constants  and  s.t.
11. Definition of Lower Bound ( notation)
if  constants  and  s.t.
12. Definition of Tight Bound ( notation)
•  is  if  is both  and
• if  exists and is equal to some number c > 0 then
13. Definition of Domination (o notation)
if
 Author: CMortty ID: 293870 Card Set: 161 Midterm 1 Updated: 2015-01-27 04:49:59 Tags: 161 Folders: Description: 161 Midterm 1 Show Answers: