Time Complexity of building a heap

Consider the following algorithm for Time Complexity of building a heap of an input array A.

[pastacode lang=”c” manual=”BUILD-HEAP(A)%20%0A%20%20%20%20heapsize%20%3A%3D%20size(A)%3B%20%0A%20%20%20%20for%20i%20%3A%3D%20floor(heapsize%2F2)%20downto%201%20%0A%20%20%20%20%20%20%20%20do%20HEAPIFY(A%2C%20i)%3B%20%0A%20%20%20%20end%20for%20%0AEND” message=”” highlight=”” provider=”manual”/] [ad type=”banner”]

What is the worst case time complexity of the above algo?
Although the worst case complexity looks like O(nLogn), upper bound of time complexity is O(n). See following links for the proof of time complexity.

Categorized in:

Analysis of Algorithm

Tagged in:

binary heap complexity, build heap algorithm, build heap algorithm c++, build heap from array, build heap visualization, heap insert time complexity, heap sort, heap sort algorithm, heap sort algorithm in c, heap sort in data structure, heap sort program in c, heap sort time complexity, heap sort time complexity analysis, heap tree, heapify, heapify algorithm, heapnote, heapsort example, heapsort example step by step, space complexity in data structure, time and space complexity, time complexity, time complexity in data structure, time complexity of algorithms, time complexity of all sorting algorithms, time complexity of an algorithm, time complexity of binary search

Share Article:

Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

View All Articles

Related Articles

J

Java Programming-Shortest path with exactly k edges in a directed and weighted graph

December 24, 2017

S

Shortest Path-Some interesting shortest path questions

December 22, 2017

Performance of loops

June 8, 2017

Analysis of Loops

May 30, 2017

Other Stories

Polynomial Time Approximation Scheme

Next Story

A Time Complexity Question

Previous Story