Heap Insert Operation Bubble Up in DSA Go - 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, it may need to move up to keep the heap order. We want to know how long this moving up takes as the heap grows.

How does the time to insert change when the heap gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func bubbleUp(heap []int, index int) {
    for index > 0 {
        parent := (index - 1) / 2
        if heap[index] <= heap[parent] {
            break
        }
        heap[index], heap[parent] = heap[parent], heap[index]
        index = parent
    }
}
    

This code moves the newly inserted element up the heap until the heap property is restored.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop that swaps the new element with its parent while it is larger.
• How many times: At most, once per level of the heap from the inserted node up to the root.

How Execution Grows With Input

Each swap moves the element one level up. The heap height grows slowly as the heap size grows.

Input Size (n)	Approx. Operations
10	About 4 swaps
100	About 7 swaps
1000	About 10 swaps

Pattern observation: The number of swaps grows slowly, roughly proportional to the height of the heap, which is much smaller than the total number of elements.

Final Time Complexity

Time Complexity: O(log n)

This means inserting an element takes time proportional to the height of the heap, which grows slowly as the heap gets bigger.

Common Mistake

[X] Wrong: "Insertion always takes constant time because we just add at the end."

[OK] Correct: After adding, the element may need to move up many levels to keep order, so the time depends on the heap height, not just adding at the end.

Interview Connect

Understanding how insertion time grows helps you explain heap efficiency clearly. This skill shows you know how data structures behave as they scale, which is key in many coding challenges.

Self-Check

"What if the heap was a min-heap instead of a max-heap? How would the bubble up time complexity change?"