Map creation (mapOf, mutableMapOf) in Kotlin - Time & Space Complexity

Time Complexity: Map creation (mapOf, mutableMapOf)

O(n)

Understanding Time Complexity

When we create a map in Kotlin, the program needs to add each item one by one. Understanding how the time needed grows as we add more items helps us write better code.

We want to know: How does the time to create a map change when we add more entries?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val numbers = listOf("one" to 1, "two" to 2, "three" to 3)
val map = mutableMapOf()
for ((key, value) in numbers) {
    map[key] = value
}
    

This code creates a mutable map and adds each pair from a list into it one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding each key-value pair to the map inside the loop.
• How many times: Once for every item in the input list.

How Execution Grows With Input

Each new item means one more add operation. So if you double the items, you double the work.

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

Pattern observation: The time 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 you add.

Common Mistake

[X] Wrong: "Adding items to a map is instant no matter how many items there are."

[OK] Correct: Each item still needs to be placed inside the map, so more items mean more work and more time.

Interview Connect

Knowing how map creation time grows helps you explain your code choices clearly and shows you understand how data structures work behind the scenes.

Self-Check

"What if we used a mapOf() with all items at once instead of adding them one by one? How would the time complexity change?"