Time Complexity: Filter and map operations
O(n)
0
0
Filter and map operations in Kafka - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time it takes to run filter and map operations changes as the data grows.
How does the number of items affect the work done by these operations?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
val numbers = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
val evenNumbers = numbers.filter(n => n % 2 == 0)
val doubled = evenNumbers.map(n => n * 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: Traversing the list twice: once for filter, once for map.
- How many times: Each operation goes through all items in the list once.
How Execution Grows With Input
As the list gets bigger, the work grows because each item is checked and then processed.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 20 (10 for filter + 10 for map) |
| 100 | About 200 (100 for filter + 100 for map) |
| 1000 | About 2000 (1000 for filter + 1000 for map) |
Pattern observation: The total work grows roughly twice as fast as the input size.
Final Time Complexity
Time Complexity: O(n)
This means the time to run filter and map grows in a straight line with the number of items.
Common Mistake
[X] Wrong: "Filter and map together make the time complexity O(nĀ²) because they are two steps."
[OK] Correct: Each step goes through the list once, so the total work adds up, not multiplies. This keeps it linear, not squared.
Interview Connect
Understanding how filter and map scale helps you explain how data processing pipelines work efficiently in real projects.
Self-Check
"What if we combined filter and map into one step? How would the time complexity change?"