Heap Insert Operation Bubble Up in DSA Javascript - Time & Space Complexity

Time Complexity: Heap Insert Operation Bubble Up

O(log n)

Understanding Time Complexity

When we add a new item to a heap, we need to keep it in order. The bubble up step moves the new item up to the right place.

We want to know how the time to do this grows as the heap gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function bubbleUp(heap) {
  let index = heap.length - 1;
  while (index > 0) {
    let parentIndex = Math.floor((index - 1) / 2);
    if (heap[index] <= heap[parentIndex]) break;
    [heap[index], heap[parentIndex]] = [heap[parentIndex], heap[index]];
    index = parentIndex;
  }
}
    

This code moves the last element up the heap until it is in the correct spot.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that compares and swaps the new element with its parent.
• How many times: At most, it runs once per level of the heap, moving from the bottom to the top.

How Execution Grows With Input

Each time we bubble up, we move one level higher in the heap tree. The heap height grows slowly as the heap gets bigger.

Input Size (n)	Approx. Operations
10	About 4 to 5 swaps
100	About 6 to 7 swaps
1000	About 9 to 10 swaps

Pattern observation: The number of steps grows slowly, roughly with the height of the heap, which increases as the logarithm of the number of items.

Final Time Complexity

Time Complexity: O(log n)

This means the time to insert and bubble up grows slowly, even if the heap gets very large.

Common Mistake

[X] Wrong: "Bubble up takes the same time no matter how big the heap is because it only moves one element."

[OK] Correct: The element may need to move up many levels, and the number of levels grows with the heap size, so time grows too.

Interview Connect

Understanding bubble up time helps you explain how heaps keep order efficiently. This skill shows you know how data structures handle growing data smoothly.

Self-Check

"What if we changed the heap to a linked structure instead of an array? How would the time complexity of bubble up change?"