Studied by 0 people
Looks like no one added any tags here yet for you.
O(n)
Starting with an empty heap, add (enqueue) n elements one at a time to build a binary heap (smallest)
O(1)
Get (but do not delete) the minimum item from a minimum heap (smallest)
O(n)
Perform insertion sort on an already sorted set of data (smallest)
O(nlogn)
Perform a Heap sort on a random set of data (smallest)
O(n^2)
Perform a Quick sort on a sorted set of data if the first item is always chosen as the pivot (smallest)
O(n)
Perform a post order traversal of a binary tree (smallest)
O(n)
Estimate for the worst case of finding the minimum in a Binary Search Tree (smallest)
O(nlogn)
Estimate for the worst case for adding (enqueueing) n items into a priority queue (smallest)
O(n)
Find the minimum key/value in a hash table (smallest)
O(n)
Find the height of a Binary Search Tree as implemented in lab 5 (smallest)
O(n)
Given a list of length n, build a binary heap using the bottom up construction method (smallest)
O(logn)
Delete (dequeue) the maximum item from a maximum binary heap (smallest)
O(1)
Add an item to a Hash Table (assume an efficient implementation of the hash table) (smallest)
O(logn)
Remove an item from a binary search tree (smallest)
O(nlogn)
Perform mergesort on a random set of data (smallest)
O(n)
Find an arbitrary item in an array (smallest)
O(1)
Delete the last (tail) node from a doubly linked list with a sentinel node implementation (smallest)
O(n)
Delete the last item from a singly linked list (assume only a reference to the head of the list) (smallest)
O(1)
Add an element to the end of an array (assume array has room for element) (smallest)
O(1)
Delete the first item from a singly linked list (assume only a reference to the head of the list) (smallest)
O(logn)
Find an arbitrary item in a well-balance binary search tree (smallest)
O(n^2)
Delete n elements form an array by repeatedly removing the first element (at index 0) (smallest)
O(n)
Insert and item at the beginning of an array (add at index 0) (smallest)
O(n)
Insertion sort (best case)
O(n^2)
Insertion sort (worst case)
O(n^2)
Insertion sort (average case)
O(n^2)
Selection sort (best case)
O(n^2)
Selection sort (worst case)
O(n^2)
Selection sort (average case)
O(nlogn)
Mergesort (best case)
O(nlogn)
Mergesort (worst case)
O(nlogn)
Mergesort (average case)
O(nlogn)
Quicksort (average case)
O(nlogn)
Quicksort (best case)
O(nlogn)
Quicksort (worst case)
O(nlogn)
Heapsort (best case)
O(nlogn)
Heapsort (average case)
O(nlogn)
Heapsort (worst case)
O(n)
Add at the beginning of an array-based list (average)
O(1)
Add at the beginning of a link-based list (average)
O(n)
Add at the end of a link-based list (average)
O(1)
Get() array-based list (average)
O(n)
get() Link-based list
O(n)
Remove from beginning array-based list
O(1)
Remove from beginning link-based list
O(n)
Stack search (worst case)
O(n)
Stack search (average case)
O(1)
Stack push (worst case)
O(1)
Stack push (average case)
O(1)
Stack pop (worst case)
O(1)
Stack pop (average case)
O(n)
Number of items in a link-based list
O(1)
Number of items in a link-based list with a size attribute
O(1)
Dequeue item from link-based queue
O(1)
Enqueue item into link-based queue
O(1)
Dequeue item from circular array-based queue
O(1)
Enqueue item into circular array-based queue
O(n)
Add item to the beginning of an array-based list (ADT)
O(n)
Add item to the middle of an array-based list (ADT)
O(1)
Add item to the end of an array-based list (ADT)
O(1)
Add item to the beginning of a link-based list (ADT)
O(n)
Add item to the middle of a link-based list (ADT)
O(1)
Add item to the end of a link-based list (ADT)
O(n)
Remove item from the beginning of an array-based list (ADT)
O(n)
Remove item from the middle of an array-based list (ADT)
O(1)
Remove item from the end of an array-based list (ADT)
O(1)
Remove item from the beginning of a (doubly) link-based list (ADT)
O(n)
Remove item from the middle of a link-based list (ADT)
O(1)
Remove item from the end of a link-based list with sentinel node (ADT)
O(n)
Find a value in an array-based list
O(n)
Find a value in a link-based list
O(1)
Find the size of an array-based list
O(1)
Get an item based on index an array-based list
O(1)
Set an index to a value in an array-based list
O(1)
Find the size of a link-based list
O(n)
Get an item based on index a link-based list
O(n)
Set an index to a value in a link-based list
O(n)
Search for a value in a doubly-linked list (average)
O(1)
Insert a value in a doubly-linked list (average)
O(1)
Delete a value in a doubly-linked list (average)
O(n)
Search for a value in a doubly-linked list (worst)
O(1)
Insert a value in a doubly-linked list (worst)
O(1)
Delete a value in a doubly-linked list (worst)
O(logn)
Search for a value in a Binary Search tree (average)
O(logn)
Insert a value in a Binary Search tree (average)
O(logn)
Delete a value in a Binary Search tree (average)
O(n)
Search for a value in a Binary Search tree (worst)
O(n)
Insert a value in a Binary Search tree (worst)
O(n)
Delete a value in a Binary Search tree (worst)
O(n)
Enqueue all n items into a Binary Heap
O(nlogn)
Dequeue all n items from a Binary Heap
O(nlogn)
Heap sort
O(n)
Bottom up heap creation
O(1)
Insert an item into a hash table
O(1)
Find an item in a hash table
O(1)
Insert an item into a Hash Table that uses separate chaining (very small linked list)
O(1)
Find an item in a Hash Table that uses separate chaining (very small linked list)
O(1)
Remove an item from a Hash Table that uses separate chaining (very small linked list)
Note 
Flashcard (92)