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

In the dynamic programming approach for LCS, the base cases are crucial for correctly initializing the dp table. Consider the following Python code snip...
Which tree traversal gives nodes in non-decreasing order for a BST?
In an adjacency matrix, checking whether edge (u,v) exists takes:
Which of the following statements about parameter passing in Python is TRUE?
In a data analysis application where two sorted linked lists need to be merged into a single sorted linked list, what is the typical time complexity of thi...
Which data structure is used in recursion?
Which of the following OWASP Top 10 risks involves insecure coding practices that allow attackers to gain access to sensitive data, such as usernames and p...
What is a "collision" in the context of hashing?
Which of the following best explains segmentation in memory management?
Which of the following is an effective countermeasure against Cross-Site Scripting (XSS) attacks in a web application?

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