Why sequences matter for performance in Kotlin - Performance Analysis

Time Complexity: Why sequences matter for performance

O(n) for lists, O(k) for sequences

Understanding Time Complexity

We want to see how using sequences changes the speed of processing collections in Kotlin.

How does the way we handle data affect how long the program takes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

// Using list operations
val resultList = numbers
    .filter { it % 2 == 0 }
    .map { it * 2 }
    .take(5)

// Using sequences
val resultSequence = numbers.asSequence()
    .filter { it % 2 == 0 }
    .map { it * 2 }
    .take(5)
    .toList()
    

This code filters even numbers, doubles them, and takes the first 5 results, once with lists and once with sequences.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Filtering and mapping over the collection.
• How many times: For lists, each operation loops over the entire list separately. For sequences, operations are combined and stop early after 5 items.

How Execution Grows With Input

When using lists, the program processes the whole list multiple times, so work grows a lot as the list grows.

Input Size (n)	Approx. Operations (List)
10	About 20 (two passes over 10 items)
100	About 200 (two passes over 100 items)
1000	About 2000 (two passes over 1000 items)

With sequences, the program stops early after finding 5 items, so work stays small even if the list grows.

Input Size (n)	Approx. Operations (Sequence)
10	About 5 (stops after 5 items)
100	About 5 (still stops early)
1000	About 5 (still stops early)

Pattern observation: Lists do more work as input grows, sequences do only as much as needed.

Final Time Complexity

Time Complexity: O(n) for lists, O(k) for sequences where k is the number of items taken.

This means lists process the whole input, but sequences can stop early and do less work.

Common Mistake

[X] Wrong: "Sequences always make code slower because they add overhead."

[OK] Correct: Sequences add a little overhead but can save a lot of work by stopping early and combining steps, making code faster for big data.

Interview Connect

Understanding how sequences change work done helps you write faster code and explain your choices clearly in real projects.

Self-Check

What if we replaced take(5) with take(500_000)? How would the time complexity change?