Binary Heap Insertion Complexity

Insertion places the new element at the next open leaf position, then restores the heap property.

Count how many levels the element may need to move up.

1. 1. Describe the insertion process

   The new element is placed at the bottom of the heap and repeatedly swapped with its parent (sift-up) while it violates the heap property.

2. 2. Bound the number of swaps

   A binary heap with $n$ elements has height $O(\log n)$, so the sift-up performs at most $O(\log n)$ swaps.

Answer: O(log n)