{"id":25031,"date":"2017-05-27T17:05:09","date_gmt":"2017-05-27T11:35:09","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25031"},"modified":"2017-05-27T17:05:09","modified_gmt":"2017-05-27T11:35:09","slug":"time-complexity-of-building-a-heap","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/time-complexity-of-building-a-heap\/","title":{"rendered":"Time Complexity of building a heap"},"content":{"rendered":"

Consider the following algorithm for Time Complexity of building a heap of an input array A.<\/p>\n

<\/div> 
BUILD-HEAP(A)     heapsize := size(A);     for i := floor(heapsize\/2) downto 1         do HEAPIFY(A, i);     end for END<\/code><\/pre> <\/div>\n[ad type=”banner”]\n
What is the worst case time complexity of the above algo?<\/strong>
\nAlthough the worst case complexity<\/a> looks like O(nLogn), upper bound of time complexity is O(n). See following links for the proof of time complexity.<\/p>\n","protected":false},"excerpt":{"rendered":"
Time Complexity of building a heap – Analysis of Algorithm – Consider the following algorithm for building a Heap of an input array A.What is the worst case<\/p>\n","protected":false},"author":1,"featured_media":25312,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70146],"tags":[71752,71751,71757,71754,71756,71755,70271,70928,70923,70873,70933,70877,71753,70878,70874,70884,70910,70880,70887,70031,70523,70022,70032,70529,70037,70142,70026],"class_list":["post-25031","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-analysis-of-algorithm","tag-binary-heap-complexity","tag-build-heap-algorithm","tag-build-heap-algorithm-c","tag-build-heap-from-array","tag-build-heap-visualization","tag-heap-insert-time-complexity","tag-heap-sort","tag-heap-sort-algorithm","tag-heap-sort-algorithm-in-c","tag-heap-sort-in-data-structure","tag-heap-sort-program-in-c","tag-heap-sort-time-complexity","tag-heap-sort-time-complexity-analysis","tag-heap-tree","tag-heapify","tag-heapify-algorithm","tag-heapnote","tag-heapsort-example","tag-heapsort-example-step-by-step","tag-space-complexity-in-data-structure","tag-time-and-space-complexity","tag-time-complexity","tag-time-complexity-in-data-structure","tag-time-complexity-of-algorithms","tag-time-complexity-of-all-sorting-algorithms","tag-time-complexity-of-an-algorithm","tag-time-complexity-of-binary-search"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25031","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25031"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25031\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/25312"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25031"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25031"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25031"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}