# 161 Midterm 1

### Card Set Information

 Author: CMortty ID: 293870 Filename: 161 Midterm 1 Updated: 2015-01-26 23:49:59 Tags: 161 Folders: Description: 161 Midterm 1 Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user CMortty on FreezingBlue Flashcards. What would you like to do?

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

What would you like to do?

Home > Flashcards > Print Preview