Question

What is the tight asymptotic time complexity of building a binary min-heap from an unsorted array of n elements using the standard bottom-up heapify approach?

Q: Answer-What is the tight asymptotic time complexity of building a binary min-heap from an unsorted array of...

Although each heapify call can cost up to Olog n, most nodes are near the bottom of the tree where sift-down work is small. Summing the actual work across all n2 internal nodes yields a series that converges to On, not On log n this is the well-known tighter bound for build-heap, proven via summing a geometric-like series over tree levels.

A O(n log n), since each of the n elements requires a heapify call costing O(log n)

B O(n), because the total work summed across all heapify calls forms a bounded series, not a simple n × log n product

C O(log n), since only the root element needs to be repositioned in the worst case

D O(n²), because each heapify call can cascade comparisons through every remaining element

E O(n log log n), due to the amortized cost of repeated halving during sift-down operations

Practice Next

More Data Structure Questions

Which data structure operates on the Last-In-First-Out (LIFO) principle, where the most recently added element is the first one to be removed?
The amortized cost of appending an element at the end of a dynamic array is:
Deletion in Red-Black Tree may require:
During insertion into an AVL tree, a node becomes unbalanced with a balance factor of -2, and the newly inserted node lies within the right subtree of that...
Which data structure uses FIFO (First In, First Out)?
What is the primary purpose of a B+ Tree in a database management system?
The keys 45, 20, 60, 10, 30, 55, 70, 25 are inserted in this order into an initially empty Binary Search Tree. What is the postorder traversal of the resul...
The time complexity of binary search is:
Using the Lomuto partition scheme with the last element as the pivot, partition the array [8, 3, 7, 4, 9, 2, 5] . What is the final index (0-indexed) of th...
Which data structure is used internally by a programming language's runtime to implement function calls and recursion?

Hey! Ask a query

🎓

Think You're Ready for RBI Grade B?

RBI Grade B 2026 Phase 1 Memory Based Paper

200 Questions with Detailed Solutions
Section-wise Coverage (GA, English, Quant & Reasoning)

Download Now 100% Free PDF

What is the tight asymptotic time complexity of building a binary min-heap from an unsorted array of n elements using the standard bottom-up heapify approach?

Detailed Solution

More Data Structure Questions

Hey! Ask a query

Please Register/Login

RBI Grade B 2026 Phase 1 Memory Based Paper