Iterating over maps in Go - Time & Space Complexity

Time Complexity: Iterating over maps

O(n)

Understanding Time Complexity

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

We ask: How does the number of steps grow when the map has more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func printMap(m map[string]int) {
    for key, value := range m {
        fmt.Println(key, value)
    }
}
    

This code goes through each item in the map and prints its key and value.

Identify Repeating Operations

• Primary operation: Looping over each key-value pair in the map.
• How many times: Once for every item in the map.

How Execution Grows With Input

As the map gets bigger, the number of print steps grows in the same way.

Input Size (n)	Approx. Operations
10	10 print steps
100	100 print steps
1000	1000 print steps

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

Final Time Complexity

Time Complexity: O(n)

This means if the map doubles in size, the time to loop through it roughly doubles too.

Common Mistake

[X] Wrong: "Looping over a map is always constant time because maps are fast."

[OK] Correct: While accessing one item is fast, looping visits every item, so time grows with map size.

Interview Connect

Understanding how looping over maps scales helps you explain your code's speed clearly and confidently.

Self-Check

"What if we nested a loop inside this loop to compare every map item with every other? How would the time complexity change?"