Data Structures and Algorithms
Midterm
Linear Search - Answer- slow --> N/2 comparisons
O(N)
Binary Search - Answer- Fast, but the array must be sorted log2(N)
Drawbacks --> insertion takes longer
O(logN)
Unordered Arrays - Answer- fast insertion O(1)
slow linear search and deletion O(N)
Ordered arrays - Answer- fast binary search O(logN)
slow insertion and deletion O(N)
Bubble Sort - Answer- Comparisons: O(N^2)
Swaps: O(N^2) (less than comparisons)
Big O: O(N^2)
Selection Sort - Answer- Comparisons: O(N^2)
Swaps: O(N)
Big O: O(N^2) --> faster than bubble sort
Insertion Sort - Answer- Comparisons: O(N^2)
--> max is N*(N-1)/2, average is N*(N-1)/4
Shifts (copies): O(N^2) --> shift is not as time consuming as a swap
--> Average: N*(N-1)/4
Big O: O(N^2) --> 1/2 the time than bubble sort
Data that is already sorted it runs in O(N) --> efficient way for arrays that are only
slightly oout of order
Enhanced Insertion sort - Answer- Comparisons: O(NlogN)
Shift: O(N^2)
Big O: O(N^2) --> faster than bubble sort
Stacks - Simple Applications - Answer- Reversing a word
Delimiter matching
Stacks and Queues - Answer- abstract data structures
Complexity O(1)
Priority Queue - Answer- dequeue is O(1) but enqueue is O(N) --> slow insertion, so
priority queue is often implemented using a heap to improve insertion time
Arrays - Answer- Advantages
Midterm
Linear Search - Answer- slow --> N/2 comparisons
O(N)
Binary Search - Answer- Fast, but the array must be sorted log2(N)
Drawbacks --> insertion takes longer
O(logN)
Unordered Arrays - Answer- fast insertion O(1)
slow linear search and deletion O(N)
Ordered arrays - Answer- fast binary search O(logN)
slow insertion and deletion O(N)
Bubble Sort - Answer- Comparisons: O(N^2)
Swaps: O(N^2) (less than comparisons)
Big O: O(N^2)
Selection Sort - Answer- Comparisons: O(N^2)
Swaps: O(N)
Big O: O(N^2) --> faster than bubble sort
Insertion Sort - Answer- Comparisons: O(N^2)
--> max is N*(N-1)/2, average is N*(N-1)/4
Shifts (copies): O(N^2) --> shift is not as time consuming as a swap
--> Average: N*(N-1)/4
Big O: O(N^2) --> 1/2 the time than bubble sort
Data that is already sorted it runs in O(N) --> efficient way for arrays that are only
slightly oout of order
Enhanced Insertion sort - Answer- Comparisons: O(NlogN)
Shift: O(N^2)
Big O: O(N^2) --> faster than bubble sort
Stacks - Simple Applications - Answer- Reversing a word
Delimiter matching
Stacks and Queues - Answer- abstract data structures
Complexity O(1)
Priority Queue - Answer- dequeue is O(1) but enqueue is O(N) --> slow insertion, so
priority queue is often implemented using a heap to improve insertion time
Arrays - Answer- Advantages
