Sequence operators (map, filter) in Kotlin - Time & Space Complexity

Time Complexity: Sequence operators (map, filter)

O(n)

Understanding Time Complexity

We want to understand how long it takes to process a list using sequence operators like map and filter.

How does the time grow when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val numbers = listOf(1, 2, 3, 4, 5)
val result = numbers
    .filter { it % 2 == 0 }
    .map { it * 2 }

This code filters even numbers from a list and then doubles each filtered number.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The filter and map each go through the list once.
• How many times: Each element is checked once in filter, then each filtered element is processed once in map.

How Execution Grows With Input

As the list size grows, the number of operations grows roughly in a straight line.

Input Size (n)	Approx. Operations
10	About 20 (10 for filter + up to 10 for map)
100	About 200 (100 for filter + up to 100 for map)
1000	About 2000 (1000 for filter + up to 1000 for map)

Pattern observation: The total work grows roughly twice the input size, so it grows linearly.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows directly in proportion to the list size.

Common Mistake

[X] Wrong: "Using both filter and map means the time grows like n squared because there are two steps."

[OK] Correct: Each step goes through the list once, so the total time adds up, not multiplies, keeping growth linear.

Interview Connect

Understanding how sequence operations scale helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if we chained three sequence operations instead of two? How would the time complexity change?"