Mutable vs immutable interfaces in Kotlin - Performance Comparison

Time Complexity: Mutable vs immutable interfaces

O(n)

Understanding Time Complexity

When working with mutable and immutable interfaces, it's important to understand how operations on these interfaces grow as data size increases.

We want to see how the choice between mutable and immutable affects the speed of common operations.

Scenario Under Consideration

Analyze the time complexity of the following Kotlin code using mutable and immutable lists.

fun processImmutableList(list: List): Int {
    var sum = 0
    for (item in list) {
        sum += item
    }
    return sum
}

fun processMutableList(list: MutableList): Int {
    var sum = 0
    for (item in list) {
        sum += item
    }
    return sum
}
    

This code sums all items in either an immutable or mutable list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each item in the list once.
• How many times: Exactly once for each element in the list.

How Execution Grows With Input

As the list gets bigger, the number of steps grows directly with the number of items.

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

Pattern observation: The work grows evenly as the list size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to sum the list grows in a straight line with the number of items.

Common Mistake

[X] Wrong: "Immutable lists are always slower because they can't change."

[OK] Correct: Both mutable and immutable lists can be traversed in the same time because reading items doesn't require changing them.

Interview Connect

Understanding how mutable and immutable interfaces affect operation speed helps you explain your choices clearly and confidently in real projects and interviews.

Self-Check

"What if we added an operation that modifies the list inside the loop? How would the time complexity change for mutable vs immutable lists?"