Term
For the selection problem, we want to get to the kth smallest element. If s is the first selected pivot, what happens after the first partitioning step? 

Definition
If s > k, look for the kth smallest element in the left partition 


Term
What defines a recurrence relation of some function R(n)? 

Definition
value of R at some other point and an initial condition 


Term
The recurrence for the sum of the first n integers is given by what? 

Definition
S(n) = S(n1) + n, S(0) = 0 


Term
Insertion sort takes time ______ in the average or worst case 

Definition


Term
Topological sorting is based on _______ 

Definition


Term
Binary search on a sorted array of n integers takes _____ time in worst case 

Definition


Term
Given a balanced binary search tree of N integers, searching for an element can be considered an example of ____________ 

Definition
decrease by a constant factor 


Term
The worst case performance of quicksort for n items is _____ 

Definition


Term
The worst case performance of mergesort for n items is _____ 

Definition


Term

Definition


Term
Breadthfirst search of a graph is best implemented using a ________ 

Definition


Term
Which representation is best for a sparsely connected graph? 

Definition


Term
Searching for an element in a hash table containing n elements takes _____ time 

Definition


Term
The worst case complexity for searching for a value in an array is ______ 

Definition


Term
Theta notation implies what? 

Definition
That lower and upper bounds are the same 


Term
What is the time for 10n^2 + 100n in theta notation? 

Definition


Term
For the N item knapsack problem, the exhaustive search takes ______ time 

Definition


Term
The convex hull of a triangle is _____ 

Definition


Term
All operations of stack are ______ 

Definition


Term
Most binary search tree algorithms typically run in time O(logN) if the tree is reasonably well balanced. What does N refer to? 

Definition
The number of nodes in the tree 


Term
Which representation is preferred for a densely connected graph? 

Definition


Term
In analyzing algorithm, name the two most important resources of any algorithm 

Definition
computation time, consumed storage 


Term
3 nested loops with each loop going from 1 through 1000 has complexity of ______ 

Definition


Term
BigO notation expresses what? 

Definition


Term

Definition
a way to find the greatest common divisor of two positive integers 


Term
For an algorithm for computing n!, what would be a natural size metric for its inputs? 

Definition


Term
When finding the largest element in a list of n numbers (using the standard scanning algorithm), can the basic operation count be different for inputs of the same size? 

Definition


Term
What is the basic operation of Euclid's algorithm? 

Definition


Term
Informally, O(g(n)) is what? 

Definition
the set of all functions with a lower or same order of growth as g(n) 

