Sequence vs collection performance in Kotlin - Performance Comparison

Time Complexity: Sequence vs collection performance

O(n)

Understanding Time Complexity

When working with data in Kotlin, we often choose between sequences and collections. Understanding how their performance changes with input size helps us pick the right tool.

We want to know how the time to process data grows as the data gets bigger.

Scenario Under Consideration

Analyze the time complexity of processing a list using a sequence versus a collection.

val numbers = (1..n).toList()

// Using collection operations
val doubledList = numbers.map { it * 2 }.filter { it % 3 == 0 }

// Using sequence operations
val doubledSequence = numbers.asSequence()
    .map { it * 2 }
    .filter { it % 3 == 0 }
    .toList()
    

This code multiplies each number by 2 and then keeps only those divisible by 3, first using collections, then sequences.

Identify Repeating Operations

Look at the repeated steps that happen for each item.

• Primary operation: Mapping and filtering each element.
• How many times: Once per element for each step in collections; once per element overall in sequences due to lazy evaluation.

How Execution Grows With Input

As the list size grows, the number of operations grows too, but differently for collections and sequences.

Input Size (n)	Approx. Operations (Collections)	Approx. Operations (Sequences)
10	About 20 (map + filter separately)	About 10 (combined steps)
100	About 200	About 100
1000	About 2000	About 1000

Pattern observation: Collections do each step fully before the next, doubling work, while sequences combine steps, doing less work overall.

Final Time Complexity

Time Complexity: O(n)

This means the time grows directly with the number of items, but sequences do fewer passes, making them faster in practice.

Common Mistake

[X] Wrong: "Sequences always take longer because they are lazy and add overhead."

[OK] Correct: Sequences avoid extra passes over data by combining steps, often making them faster for large data sets.

Interview Connect

Knowing how sequences and collections handle data helps you explain efficient data processing choices clearly, a valuable skill in many coding discussions.

Self-Check

What if we added a sorting step after filtering? How would that affect the time complexity for sequences and collections?