Time Complexity: Map transformation
O(n)
0
0
Map transformation in Kotlin - Time & Space Complexity
Understanding Time Complexity
When we transform a map, we want to know how the time it takes changes as the map gets bigger.
We ask: How does the work grow when the map has more entries?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
val originalMap = mapOf("a" to 1, "b" to 2, "c" to 3)
val transformedMap = originalMap.mapValues { (key, value) -> value * 2 }
println(transformedMap)
This code takes each entry in the map and doubles its value, creating a new map.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: The mapValues function visits each key-value pair once.
- How many times: Exactly once for each entry in the map.
How Execution Grows With Input
As the map gets bigger, the work grows in a straight line with the number of entries.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 visits to entries |
| 100 | 100 visits to entries |
| 1000 | 1000 visits to entries |
Pattern observation: Doubling the number of entries doubles the work.
Final Time Complexity
Time Complexity: O(n)
This means the time to transform the map grows directly with the number of entries.
Common Mistake
[X] Wrong: "Transforming a map is instant no matter the size."
[OK] Correct: Each entry must be visited once, so bigger maps take more time.
Interview Connect
Understanding how map transformations scale helps you write efficient code and explain your choices clearly.
Self-Check
What if we used mapKeys instead of mapValues? How would the time complexity change?