Exam Flashcards
Analysis of Selection Sort
Best case:
Array in sorted order
Comparisons: O(n^2)
Time: O(n^2)
Average case:
Comparisons: O(n^2)
Time: O(n^2)
Worst case:
Array in reverse order
Comparisons: O(n^2)
Time: O(n^2)
Analysis of Merge Sort
Best case:
Comparisons: O(n log n)
Time: O(n log n)
Average case:
Comparisons: O(n log n)
Time: O(n log n)
Worst case:
Comparisons: O(n log n)
Time: O(n log n)
Analysis of Insertion Sort
Best case:
Array in sorted order
Comparisons: O(n)
Time: O(n)
Average case:
Comparisons: O(n^2)
Time: O(n^2)
Worst case:
Array in reverse order
Comparisons: O(n^2)
Time: O(n^2)
Analysis of Quick Sort
Best case:
Comparisons: O(n log n)
Time: O(n log n)
Average case:
Comparisons: O(n log n)
Time: O(n log n)
Worst case:
When the list is sorted and left most element is chosen as the pivot
Comparisons: O(n^2)
Time: O(n^2)
Analysis of Shell Sort
Best case:
Comparisons: O(n log n)
Time: O(n log n)
Average case:
Comparisons: O(n^4/3)
Time: O(n(log(n))^2)
Worst case:
Comparisons: O(n^3/2)
Time: O(n(log(n))^2)
Given a list of size n, for which gap value is shell sort the same as insertion sort?
1
Analysis of Sequential Search
Best case:
O(1)
Average case:
O(n)
Worst case:
O(n)
Comparisons:
n
n+1/ 2
Analysis of Binary Search
Best case:
O(log n)
Average case:
O(log n)
Worst case:
O(log n)
Comparisons:
log n
2 log n (average)
n (best)
Pros and Cons of Selection Sort
Pros:
Simple implementation
Cons:
Inefficient on large lists
Pros and Cons of Merge Sort
Pros:
Quicker for larger lists
Unlike insertion sort, it doesn’t go through the list multiple times
Cons:
Comparatively slower than other algorithms for smaller data sets
Pros and Cons of Insertion Sort
Pros:
Simple implementation
Extremely efficient on small lists
More efficient than bubble and selection sort
Cons:
Much less efficient on large lists
Pros and Cons of Quick Sort
Pros:
An in-place sorting algorithm does not use additional memory space while sorting.
Cons:
Not very stable
Binary Search Tree Analysis
Average:
O(log n)
Worst:
O(n)
Hash Table Analysis
Average:
O(1)
Worst:
O(n)
Calculate the number of comparisons insertion sort
Best Case:
n - 1
Worst Case:
n(n-1)/2
Calculate the number of comparisons selection sort
n(n-1)/2
Benefits of Hash search over Binary Search
Hash search has O(1) for:
Search
Insert
Delete
Binary only has O(log n)
Benefits of Binary Search over Hash Search
Binary Search can get all keys in sorted order by just doing an inorder traversal
Binary Search is easier to implement whereas Hash Search general requires importing libraries
An important advantage of quadratic probing over Linear Probing
Quadratic Probing is far less prone to clustering whereas Linear Probing forms groups by placing elements one after another thus clustering occurs which can slow down the algorithm
What is BFS (Breadth First Search) used for?
- Shortest Path in an unweighted graph
- Underpins other algorithms
- Peer-to-peer networking
- Cycle detection
What is DFS (Depth First Search) used for?
- Finding connected components in subgraphs
- Maze solving and generation
- Solving problems which have only one possible solution
- cycle detection
- Scheduling
Prim’s algorithm is:
- Built from a starting vertex
- Similar to BFS
Kruskal’s algorithm is:
- Built by picking edges anywhere in a graph
- Priority queue
How do you know if an Euler’s PATH exists in a graph?
if and only if there are no more than 2 vertices with an odd number of edges
How do you know if an Euler’s CYCLE exists in a graph?
if and only if all vertices have an even number of edges
