1.What is the Big-O of 3T(n/3) + 3n^4?
- A.O(n^4)
- B.O(n^3)
- C.O(n!)
- D.O(n^⅓)
Given an input array A = [4, 1, 3, 2, 16, 9, 10, 14, 17, 6], how is the array transformed by build_min_heap?
A.[4, 2, 3, 1, 14, 9, 10, 17, 6, 16]
- B.[1, 2, 3, 6, 14, 9, 10, 17, 4, 16]
- C.[1, 2, 3, 14, 4, 9, 10, 17, 16, 6]
- D.[1, 4, 3, 2, 14, 9, 10, 17, 6, 16]
All recurrences can be handled by the master theorem.
A. True
- B. False
- Trace through the heapsort of [6, 3, 8, 12, 1, 2, 34, 5, 7]. Show the array after buildheap and after each heapify.
Answer: Array: [6,3,8,12,1,2,34,5,7]
Build Heap 1 - [34, 12, 8, 7, 1, 2, 6, 5, 3]
After Heapify 1: [3, 12, 8, 7, 1, 2, 6, 5 ][34]
Build Heap 2: [12, 7, 8, 5, 1, 2, 6, 3] 34
After Heapify 2: [3, 7, 8, 5, 1, 2, 6][12, 34]
Build Heap 3: [8, 7, 6, 5, 1, 2, 3] 12, 34
After Heapify 3: [3, 7, 6, 5, 1, 2][8, 12, 34]
Build Heap 4: [7, 5, 6, 3, 1, 2] 8, 12, 34
After Heapify 4: [2, 5, 6, 3, 1][7, 8, 12, 34]
Build Heap 5: [6, 5, 2, 3, 1] 7, 8, 12, 34
After Heapify 5: [1, 5, 2, 3][6, 7, 8, 12, 34]
Build Heap 6: [5, 3, 2, 1] 6, 7, 8, 12, 34
After Heapify 6: [1, 3, 2][5, 6, 7, 8, 12, 34]
Build Heap 7: [3, 1, 2] 5, 6, 7, 8, 12, 34
After Heapify 7: [2 ,1][3, 5, 6, 7, 8, 12, 34]
Build Heap 8: [2, 1] 3, 5, 6, 7, 8, 12, 34
After Heapify 8: [1][2, 3, 5, 6, 7, 8, 12, 34]
Sorted Heap:[1, 2, 3, 5, 6, 7, 8, 12, 34]
- Give at least two recurrences for each:
1 - f(n) = Theta(lg n)
2 - f(n) = Theta(n)
3 - f(n) = Theta(n^2 lg n)
And for each one, choose a recurrence you wrote and list the work done at the first few levels of the recurrence tree.
Answer: