Fill in the blank: 1. ?(f(n)) = {set of functions that grow _ as f(n)} 2. The nu
ID: 3919860 • Letter: F
Question
Fill in the blank:
1. ?(f(n)) = {set of functions that grow _ as f(n)}
2. The number of edges in a simple graph G = (V,E) is at most _
3. In Quick Sort, the number of comparisons made by Partition must be at least: _
4. The data data structures useful in Prim’s Algorithm and Kruskal’s Algorithm are _ and _ respectfully.
5. The number of vertices and edges in a graph are known as _ and _ of a graph, respectfully.
6. An acyclic graph is called a _ if connected or a _ if not connected.
7. The best algorithm for finding the kth largest element in an array, A[1..n], of distinct elements is in ?(_).
8. In Quick Sort, the number of comparison made by Partition(A[1,...,n], left, right) must be at least_
Explanation / Answer
1. as small as
2. n(n-1)/2
for a simple graph.
3. n logn comparisons
4. graph, heap
In Prim's algorithm graph data structure is required and in Kruskal's Heap is required.
6. tree, forest
7. n
Need to scan all the elements at least once.
8. nlogn
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.