Time Complexity: Why immutable collections are default
O(n)
0
0
Why immutable collections are default in Kotlin - Performance Analysis
Understanding Time Complexity
We want to understand how using immutable collections affects the time it takes for programs to run.
Specifically, we ask: How does making collections unchangeable by default impact the number of steps a program takes?
Scenario Under Consideration
Analyze the time complexity of creating and using immutable collections in Kotlin.
val list = listOf(1, 2, 3, 4, 5)
val newList = list + 6
val filteredList = newList.filter { it % 2 == 0 }
println(filteredList)
This code creates an immutable list, adds an element by making a new list, then filters even numbers.
Identify Repeating Operations
Look for loops or repeated steps in the code.
- Primary operation: Traversing the list to filter elements.
- How many times: Once for filtering, once for adding (which copies the list).
How Execution Grows With Input
As the list gets bigger, copying and filtering take more steps.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 20 steps (copy + filter) |
| 100 | About 200 steps |
| 1000 | About 2000 steps |
Pattern observation: The steps grow roughly twice as fast as the list size because of copying and filtering.
Final Time Complexity
Time Complexity: O(n)
This means the time to add or filter grows in a straight line with the number of items.
Common Mistake
[X] Wrong: "Immutable collections are slow because they always copy everything."
[OK] Correct: While some copying happens, Kotlin uses smart ways to share data internally, so not everything is copied every time.
Interview Connect
Understanding how immutable collections work helps you write safer code and explain your choices clearly in interviews.
Self-Check
"What if we changed the immutable list to a mutable list? How would the time complexity of adding an element change?"