Shared Flashcard Set

Details

csc 345 Algorithm Runtimes
University of Arizona CSC 345 Algorithm Runtime flashcards
25
Computer Science
07/19/2011
Click here to study/print these flashcards.

Create your own flash cards! Sign up here.

Additional Computer Science Flashcards

 

 

Cards

Term
Splay Tree -- Insert/Sort/Delete -- Average
 Definition
O( log(n) )
Term
Splay Tree -- Insert/Sort/Delete -- Worst
 Definition
O(n)
Term
Heapsort
 Definition
O( n*log(n) )
Term
Heap -- Build
 Definition
O( n*log(n) )
Term
Heap -- Insert/Remove(any)
 Definition
O( log(n) )
Term
B-Tree -- Any
 Definition
O( t*log_t(n) )
Term
AVL Tree -- Any
 Definition
O( log(n) )
Term
BST -- Insert/Remove/Search -- Average
 Definition
O( log(n) )
Term
BST -- Insert/Remove/Search -- Worst
 Definition
O(n)
Term
Hashing -- Insert (chaining)
 Definition
O(1)
Term
Hashing (chaining) -- Remove/Search -- Worst
 Definition
O(n)
Term
Hashing -- Remove/Search -- Average
 Definition
O(1)
Term
Insertion Sort -- Best
 Definition
O(n)
Term
Insertion Sort -- Worst/Average
 Definition
O(n^2)
Term
Bubble Sort -- all
 Definition
O(n^2)
Term
Selection Sort -- Comparisons
 Definition
O(n^2)
Term
Selection Sort -- Swaps
 Definition
O(n)
Term
Merge Sort -- All
 Definition
O( n*log(n) )
Term
Quicksort -- Best
 Definition
O( n*log(n) )
Term
Quicksort -- Worst
 Definition
O(n^2)
Term
Shell Sort runtime (optimum gap sequence)
 Definition
O( n*log^2(n) )
Term
Counting Sort
 Definition
O(n+k)
Term
Dijkstra's Algorithm runtime
 Definition
O((m+n)*log(n)
Term
Bellman-Ford Algorithm
 Definition
O(m*n)
Term
Radix Sort
 Definition
O( k*(n+r) )