# Shared Flashcard Set

## Details

03 Invitation to Computer Science
Chapter 3 - The Efficiency of Algorithms
21
Computer Science
Not Applicable
03/03/2014

Term
 The study of the efficiency of algorithms
Definition
 1)    analysis of algorithms
Term
 An algorithm that doesn't solve a problem, but provides a close approximation to a solution
Definition
 2)    approximation algorithm
Term
 Running a program on many data sets to be sure its performance falls within required limits; timing the same algorithm on two different machines
Definition
 3)    benchmarking
Term
 An algorithm that searches for a target value in a sorted list by checking at the midpoint and then repeatedly cutting the search section in half
Definition
 4)    binary search algorithm
Term
 A sorting algorithm that makes multiple passes through the list from front to back, each time exchanging pairs of entries that are out of order
Definition
 5)    bubble sort algorithm
Term
 An algorithm's careful use of time and space resources
Definition
 6)    efficiency
Term
 An algorithm whose work varies as some constant to the power of the input size n
Definition
 7)    exponential algorithm
Term
 floating-point operations per second
Definition
 8)    flops
Term
 A problem for which no polynomially bounded solution exists
Definition
 9)    intractable
Term
 The efficiency classification of an algorithm whose work varies as a constant times lg(n)
Definition
 10)    order of magnitude lg n
Term
 The efficiency classification of an algorithm whose work varies as a constant times the input size n
Definition
 11)    order of magnitude n
Term
 The efficiency classification of an algorithm whose work varies as a constant times the square of the input size n
Definition
 12)    order of magnitude n2
Term
 An algorithm that does less work than some polynomial expression of the input size n
Definition
 13)    polynomially bounded
Term
 The task of finding a specific value in a list of values (or determining if that value is not there)
Definition
 14)    searching
Term
 A sorting algorithm that keeps moving larger items toward the back of the list
Definition
 15)    selection sort algorithm
Term
 An algorithm that searches for a target value in a random list by checking each list item in turn
Definition
 16)    sequential search algorithm
Term
 A variation of the sequential search algorithm that requires a sorted list and stops once it has passed the place where the target could occur
Definition
 17)    short sequential search
Term
 A variation of the bubble sort algorithm that stops when no exchanges occur on a given pass
Definition
 18)    smart bubble sort
Term
 The task of putting a list of values into numeric or alphabetical order
Definition
 19)    sorting
Term
 For more study material on this topic click here and go to my Computer Science Study Help page
Definition
 For more study material on this topic click here and go to my Computer Science Study Help page
Term
 For more study material on this topic click here and go to my Computer Science Study Help page
Definition
 For more study material on this topic click here and go to my Computer Science Study Help page
Supporting users have an ad free experience!