Sequence creation methods in Kotlin - Time & Space Complexity

Time Complexity: Sequence creation methods

O(n)

Understanding Time Complexity

When we create sequences in Kotlin, it is important to know how the time to build them grows as we add more elements.

We want to understand how the work changes when the sequence size changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val seq = sequence {
    for (i in 1..n) {
        yield(i * 2)
    }
}
val list = seq.toList()
    

This code creates a sequence of doubled numbers from 1 to n, then converts it to a list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that yields each element one by one.
• How many times: Exactly n times, once for each number from 1 to n.

How Execution Grows With Input

As n grows, the number of times we run the loop and create elements grows directly with n.

Input Size (n)	Approx. Operations
10	About 10 loop runs and yields
100	About 100 loop runs and yields
1000	About 1000 loop runs and yields

Pattern observation: The work grows evenly as n grows; doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to create and collect the sequence grows in a straight line with the number of elements.

Common Mistake

[X] Wrong: "Sequences create all elements instantly, so time does not depend on n."

[OK] Correct: Sequences generate elements lazily, but when converting to a list, all elements are created one by one, so time grows with n.

Interview Connect

Understanding how sequence creation scales helps you explain efficient data processing and lazy evaluation in real projects.

Self-Check

"What if we replaced the sequence with a simple list builder? How would the time complexity change?"