Big-oh notation Question! Short answer questions: two sentences or formulas at m
ID: 3557029 • Letter: B
Question
Big-oh notation Question!
Short answer questions: two sentences or formulas at most. 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? 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)? Give an example of a function f(n) such that f(n) = o(n2), but n2 = o(nf(n)) (no proof needed). If your implementation of Quicksort usually runs in time 28nlog2n, and your InsertionSort runs in time 7n2, 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.) 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 deleted in O(log n) time, and (iii) is always perfectly balanced? State the invariant it satisfies.Explanation / Answer
1.Since,the height of a randomly built binary search tree is O(lg n), so that basic dynamic-set operations take (lg n) time. so for each element to insert in a comparision based bst, it talkes O(lg n) time. so for n elements, It will take O(nlg n) time.
2.yes max_heap inserts elements in O( n) time but it also has a heapify function in it which takes O(lg n) time..So total time is O(nlg n).
3......
4. we can check it by equating both i.e..
28n log n= 7n^2
4 log n=n
which gives n<=15
5.required time = 1000000 log(1000000) /10000 log(10000) = 150 times
6. binary heap
*The tree is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
*All nodes are either [greater than or equal to] or [less than or equal to] each of its children, according to a comparison predicatedefined for the heap.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.