Home > Flashcards > Print Preview
The flashcards below were created by user
laonese
on FreezingBlue Flashcards. What would you like to do?

Average case, worst case, and memory usage of merge sort.
 Average: O(nlogn)
 Worst: O(nlogn)
 Best: O(nlogn)
 Memory usage: O(n) additional

Average case, worst case, and memory usage for quick sort.
 Average: O(nlogn)
 Worst: O(n^2)
 Best: O(nlogn)
 Memory usage: O(1)

How does a sequential search work?
Start at the first element in the list and continue until either the item is found in the list or the entire list is searched.

Average and worst case scenario for sequential(linear) search
O(n)

How does a binary search tree work?
List must be ordered. Uses the divide and conquer approach. Compare item with middle of list. If item equals middle, then found, else if the item is less, restrict search to lower half and vice versa if item is higher

What is the best and worst case for binary search?
O(log(n))

How does hash table search work?
Data is first organized by the hash table which is stored in an array. To find out if something is stored in the hash table, a hash function used to a key. This gives the address of the item in the hash table.

How does selection sort work?
Divides the data into two sublist of items sorted and remaing items to be sorted. Finds the smallest element in the unsorted sublist, exchanging it with the leftmost unsorted element and moving the sublist boundaries one element to the right.

Average case, worst case, and memory usage of selection sort.
 Average: O(n^2)
 Worst: O(n^2)
 Memory Usage:

How does bubble sort work?
Compares each pair of adjacent items and swapping them if they are in the wrong order. This is repeated until no swaps are needed.

Average and worst case for bubble sort
 Average: O(n^2)
 Worst: O(n^2)
 Best: O(n)

How does insertion sort work?
Iterate through the list and move one element at a time to the correct location within the sorted list.

Average and worst case for insertion sort
 Average: O(n^2)
 Worst: O(n^2)
 Best: O(n)

How does quicksort work?
A divide and conquer algorithm. First divides a large array into two small subarrays: lower and higher elements. Then recursively sort the subarrays. Pick a pivot, reorder array so all elements lower than pivot on left and higher on right. Apply same steps to subarray of elements.

How does mergesort work?
Divide unsorted list into smallest unit of 1 element, then compare each element with the adjacent list to sort and merge them.

How does heapsort work?
First a heap is built out of the data. Then a sorted array is created by repeatedly removing the largest element from the heap and inserting it into the array.

Average and worst case for heap sort
 Average: O(nlogn)
 Worst: O(nlogn)
 Best: O(nlogn)

How does bucket sort work?
Set up an array of buckets. Put objects into buckets. Sort each bucket. Gather the results and put all elements back into the original array.




What are AVL trees?
A selfbalancing binary search tree.

What are Btrees?
A tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions. A node can have more than two children.

What are B+trees?
Can be viewed as BTrees in which each node contains only keys and to which an additional level is added at the bottom with linked leaves. Primary value is storing data for efficient retrieval in blockoriented storage context.

