Short answer questions: two sentences or formulas at most. (a) Why can't there be any kind...

 

Transcribed Image Text:

Short answer questions: two sentences or formulas at most. (a) Why can't there be any kind of comparison-based binary search tree that allows any sequence of n elements to be inserted in O(n) total time? (b) Wait a second-by putting n elements into a vector and calling make heap, one can effectively insert n elements into a heap in O(n) total time. Why isn't that a violation of what we just said in (a)? (c) Give an example of a function f(n) such that f(n) = o(n), but n = o(nf(n)) (no proof needed). (d) If your implementation of Quicksort usually runs in time 28n log, n, and your InsertionSort runs in time 7n, below what value of n is it faster to call InsertionSort than (recursively) call Quicksort? How many times longer does it typically take HeapSort to sort a 1,000,000-item array than a 10,000-item array? (You have full information to answer this and do not need a calculator.) (f) What kind of binary tree (i) allows the maximum element to be found in O(1) time, (ii) allows any element to be inserted and allows the maximum element to be deletedate in O(log n) time, and (iii) is always perfectly balanced? State the invariant it satisfies.Settin Short answer questions: two sentences or formulas at most. (a) Why can't there be any kind of comparison-based binary search tree that allows any sequence of n elements to be inserted in O(n) total time? (b) Wait a second-by putting n elements into a vector and calling make heap, one can effectively insert n elements into a heap in O(n) total time. Why isn't that a violation of what we just said in (a)? (c) Give an example of a function f(n) such that f(n) = o(n), but n = o(nf(n)) (no proof needed). (d) If your implementation of Quicksort usually runs in time 28n log, n, and your InsertionSort runs in time 7n, below what value of n is it faster to call InsertionSort than (recursively) call Quicksort? How many times longer does it typically take HeapSort to sort a 1,000,000-item array than a 10,000-item array? (You have full information to answer this and do not need a calculator.) (f) What kind of binary tree (i) allows the maximum element to be found in O(1) time, (ii) allows any element to be inserted and allows the maximum element to be deletedate in O(log n) time, and (iii) is always perfectly balanced? State the invariant it satisfies.Settin

Answer rating: 100% (QA)

a It is not possible to have a comparisonbased binary search tree that allows any sequence of n elem... View the full answer