Partition for splitting in Kotlin - Time & Space Complexity

Time Complexity: Partition for splitting

O(n)

Understanding Time Complexity

When we split a list into two parts based on a condition, we want to know how long it takes as the list grows.

How does the work increase 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 (even, odd) = numbers.partition { it % 2 == 0 }
println("Even numbers: $even")
println("Odd numbers: $odd")
    

This code splits a list of numbers into two 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 number once to see if it is even or odd.
• How many times: Exactly once for every item in the list.

How Execution Grows With Input

As the list gets bigger, the program checks each number one time.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

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 split the list grows in a straight line with the number of items.

Common Mistake

[X] Wrong: "Partitioning takes more time because it creates two lists and does extra work."

[OK] Correct: The main work is just checking each item once; creating two lists is done while checking, so it does not add extra loops.

Interview Connect

Understanding how partition works helps you explain how simple loops handle splitting data efficiently in real programs.

Self-Check

"What if we changed the condition to check each item twice inside the partition? How would the time complexity change?"