Time Complexity: Filter and filterNot
O(n)
0
0
Filter and filterNot in Kotlin - Time & Space Complexity
Understanding Time Complexity
When we use filter or filterNot in Kotlin, we want to keep or remove items from a list based on a rule.
We ask: How does the time to do this change 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, 6)
val evenNumbers = numbers.filter { it % 2 == 0 }
val oddNumbers = numbers.filterNot { it % 2 == 0 }
This code creates a list of numbers, then makes two new lists: one with even numbers and one with odd numbers.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Checking each item in the list once to see if it matches the condition.
- How many times: Once for each item in the list (one pass per filter/filterNot call).
How Execution Grows With Input
Each item in the list is checked once per filter call, so the work grows as the list grows.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 10 checks per filter call |
| 100 | About 100 checks per filter call |
| 1000 | About 1000 checks per filter call |
Pattern observation: The number of checks grows directly with the size of the list.
Final Time Complexity
Time Complexity: O(n)
This means the time to filter grows in a straight line as the list gets bigger.
Common Mistake
[X] Wrong: "filter and filterNot are instant no matter how big the list is."
[OK] Correct: Each item must be checked, so bigger lists take more time.
Interview Connect
Understanding how filtering scales helps you write clear and efficient code, a skill that shows you think about how programs work in real life.
Self-Check
"What if we combined filter and filterNot into one pass? How would the time complexity change?"