Question

What is the worst-case time (in Big-O) for building a Min-Heap of N nodes, using bulk insertion (bottom-up construction), assuming comparing two keys takes constant time. Justify your answer. You may assume N = 2^h+1 – 1, for simplicity.

Answer 1

Worst case time complexity in bigO notation is upper bound an algorithm may take ,

min -heap , is a type of priority queue which always maintain minimum element as root node. ,

building min-heap using bottom-up construction ,

in build min-heap operation loops are executed from n/2 to 1 , here n is number of node , means it always execeute from last parent node and execute till root node , inside this loop heapify operation is also executing , and it will take O(log(n)) time , so overall complexity is * log(n) , , here h is height of min -heap.

after solving above equation will be O(n)