S4-P4 Flashcards
*
1
A
We can note an interesting observation about max-heap.An element x at ith level has i – 1 ancestors. By the property of max-heaps, these i – 1 ancestors are guaranteed to be greater than x. This implies that x cannot be among the greatest i – 1 elements of the heap. Using this property, we can conclude that the kth greatest element can have a level of at most k. We can reduce the size of the max-heap such that it has only k levels. We can then obtain the kth greatest element by our previous strategy of extracting the maximum element k times.
Note that the size of the heap is reduced to a maximum of 2^k – 1, therefore each heapify operation will take O(log 2k) = O(k) time.
4
A
Note On n=2^k -1: We say it’s a full tree because we know it’s a complete tree (since it’s a min-heap) and we know the number of nodes.
3
A
Note On Creating A Heap Tree: The order is θ(n)
Note On BST Inorder: The order is θ(n)
Note On Option 4: We can’t sort in orders smaller than n
Note On Option 1,2: We cannot sort any n numbers with an algorithm of θ(n) order.The lower bound for comparison-based sorting algorithms is Ω(n log n) , which means that any comparison-based sorting algorithm must take at least Ω(n log n) time to sort n elements. This lower bound is based on the decision tree model, which assumes that the algorithm can only gain information about the input by comparing pairs of elements. Therefore, any algorithm that sorts n elements by making fewer than Ω(n log n) comparisons cannot be a comparison-based sorting algorithm. However, there are non-comparison-based sorting algorithms, such as counting sort, radix sort, and bucket sort, that can sort n elements in O(n) time complexity. These algorithms do not rely on comparisons between elements, but they have specific requirements and limitations, such as the range of the input values and the available memory.
Note On Decision Trees: The decision tree model is a theoretical model used to analyze the time complexity of comparison-based sorting algorithms.
1
A
Note on BST: By combining the inorder traversal with either the preorder or postorder traversal, we can determine the root node of the binary tree and the order in which the nodes are visited in a preorder or postorder traversal of the binary tree. This information is sufficient to construct a unique binary tree. and in BST the inorder sequence is the sorted node numbers.
End of P4
