Map creation in Go - Time & Space Complexity

Time Complexity: Map creation

O(n)

Understanding Time Complexity

When we create a map in Go, we want to know how the time it takes changes as the map gets bigger.

We ask: How does adding items to a map affect the time needed?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

func createMap(n int) map[int]int {
    m := make(map[int]int)
    for i := 0; i < n; i++ {
        m[i] = i * 2
    }
    return m
}

This code creates a map and adds n key-value pairs, where each key is an integer and the value is double the key.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Inserting a key-value pair into the map inside the loop.
• How many times: Exactly n times, once for each number from 0 to n-1.

How Execution Grows With Input

As n grows, the number of insertions grows the same way.

Input Size (n)	Approx. Operations
10	10 insertions
100	100 insertions
1000	1000 insertions

Pattern observation: The work grows directly with the number of items added.

Final Time Complexity

Time Complexity: O(n)

This means the time to create the map grows in a straight line with the number of items added.

Common Mistake

[X] Wrong: "Adding items to a map takes the same time no matter how many items are already there."

[OK] Correct: Each insertion takes some time, so more items mean more total time, even if each insert is fast.

Interview Connect

Understanding how map creation time grows helps you explain how data structures behave as they get bigger, a useful skill in many coding situations.

Self-Check

"What if we changed the map to store slices instead of integers? How would the time complexity change?"