Answer the questions in the space provided. The average running time of insert o
ID: 3865520 • Letter: A
Question
Answer the questions in the space provided. The average running time of insert operation for a BST with N nods is: _____ When sorting n records, Quicksort has average-case and best case cost of: _____ If quadratic probing is used, and the table size is prime, then a new element can always be inserted if: _____ A graph with n vertices and m edges is represented using an adjacency matrix. What is the lower bound for any algorithm that traverses all the edges of the graph? The const Object & front() const operation for list containers _____Explanation / Answer
1. O(log n)
For single insert operation it takes just log n time to check what would be the position of the object to be inserted.
2. O(nlogn)
For both the cases the answer is same. Best case occurs when pivot we pick happens to divide the array into two equal parts and average case can be anything.
3. the table is at least half empty
If you recall, this is a theorem. Quadratic probing just uses quadratic function to manage the collisions in hash table.
4. O(n^2)
The lower bound is nothing but the least amount of steps or time taken to traverse all the edges of the graph. For adjacency matrix you have to travel all the rows and column to traverse the graph.
5. The question is quite unclear. However, const when applied on anything then it justs prevents from modifying the value of the member during it's complete life. It also enables compiler optimisations by specifying that attempts to modify it are undefined behaviour.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.