{"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":"<p>Consider the following algorithm for Time Complexity of building a heap of an input array A.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201dBUILD-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\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n<p><strong>What is the worst case time complexity of the above algo?<\/strong><br \/>\nAlthough the <a href=\"https:\/\/www.wikitechy.com\/technology\/worst-average-and-best-cases\/\">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":"<p>Time Complexity of building a heap &#8211; Analysis of Algorithm &#8211; 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}]}}