title: Time complexity of inserting in to a heap
body: <p>I am trying to mostly understand the reasoning behind the Big O and Omega of inserting a new element in a heap. I know I can find answers online but I really like having a thorough understanding rather than just finding answers online and just memorizing blindly.</p>
  
  <p>So for instance if we have the following heap (represented in array format)</p>
  
  <pre><code> [8,6,7,3,5,3,4,1,2] 
  </code></pre>
  
  <p>If we decide to insert a new element "4" our array will look like this now</p>
  
  <pre><code> [8,6,7,3,5,3,4,1,2,4] 
  </code></pre>
  
  <p>It would be placed in index 9 and since this is a 0th index based array its parent would be index 4 which is element 5. In this case we would not need to do anything because 4 is &lt; 5 and it does not violate the binary heap property. So best case is OMEGA(1). </p>
  
  <p>However if the new element we insert is 100 then we would have to call the max-heapify function which has running time of O(log n) and therefore in the worst case inserting a new element in the heap takes O(log n).</p>
  
  <p>Can someone correct me if I am wrong because I am not sure if my understanding or reasoning is 100%?</p>