{"id":27044,"date":"2018-01-02T21:00:53","date_gmt":"2018-01-02T15:30:53","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27044"},"modified":"2018-01-02T21:00:53","modified_gmt":"2018-01-02T15:30:53","slug":"time-complexity-building-heap-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/time-complexity-building-heap-2\/","title":{"rendered":"Time Complexity of building a heap"},"content":{"rendered":"<p>Consider the following algorithm for building a Heap of an input array A.<span id=\"more-12580\"><\/span><\/p>\n<pre>BUILD-HEAP(A) \r\n    heapsize := size(A); \r\n    for i := floor(heapsize\/2) downto 1 \r\n        do HEAPIFY(A, i); \r\n    end for \r\nEND\r\n<\/pre>\n<p><em>What is the worst case time complexity of the above algo?<\/em><br \/>\nAlthough 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.<\/p>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>Time Complexity of building a heap &#8211; Heap &#8211; Although the worst case complexity looks like O(nLogn), upper bound of time complexity is O(n).<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[73012,80127],"tags":[71752,71751,71754,80684,80686,71755,71753,80685],"class_list":["post-27044","post","type-post","status-publish","format-standard","hentry","category-data-structures","category-heap","tag-binary-heap-complexity","tag-build-heap-algorithm","tag-build-heap-from-array","tag-build-heap-geeksforgeeks","tag-build-max-heap","tag-heap-insert-time-complexity","tag-heap-sort-time-complexity-analysis","tag-heapify-geeksforgeeks"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27044","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=27044"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27044\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27044"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27044"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27044"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}