List creation (listOf, mutableListOf) in Kotlin - Time & Space Complexity

Time Complexity: List creation (listOf, mutableListOf)

O(n)

Understanding Time Complexity

When we create lists in Kotlin, it is helpful to know how the time it takes grows as the list gets bigger.

We want to understand how the work done changes when we add more items to the list.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val numbers = listOf(1, 2, 3, 4, 5)

val mutableNumbers = mutableListOf()
for (i in 1..5) {
    mutableNumbers.add(i)
}
    

This code creates a fixed list with 5 items and a mutable list where items are added one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding items to the mutable list inside a loop.
• How many times: The add operation runs 5 times, once for each item.

How Execution Grows With Input

When the list size grows, the number of add operations grows the same way.

Input Size (n)	Approx. Operations
10	10 add operations
100	100 add operations
1000	1000 add operations

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

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Creating a list with many items is instant and does not depend on size."

[OK] Correct: Each item must be added or copied, so more items mean more work and more time.

Interview Connect

Understanding how list creation time grows helps you explain efficiency when working with collections in real projects.

Self-Check

"What if we used a different data structure like a linked list? How would the time complexity of adding items change?"