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?"

Practice

1. Which of the following is the correct way to directly create a sequence from a fixed set of values in Kotlin?

easy

A. val seq = sequenceOf(1, 2, 3)

B. val seq = listOf(1, 2, 3).asSequence()

C. val seq = arrayOf(1, 2, 3).toSequence()

D. val seq = sequence(1, 2, 3)

Solution

1. Step 1: Understand sequence creation from fixed values

   The function sequenceOf() creates a sequence directly from given values.

2. Step 2: Check each option's validity

   val seq = sequenceOf(1, 2, 3) uses sequenceOf(1, 2, 3), which is correct. val seq = listOf(1, 2, 3).asSequence() creates a list then converts to sequence, which is valid but not direct creation. val seq = arrayOf(1, 2, 3).toSequence() uses a non-existent toSequence() method on array, which is invalid. val seq = sequence(1, 2, 3) uses sequence() which is not a valid function for this purpose.

3. Final Answer:

   val seq = sequenceOf(1, 2, 3) -> Option A

4. Quick Check:

   Direct sequence creation = sequenceOf(...) [OK]

Hint: Use sequenceOf() to create sequences from fixed values [OK]

Common Mistakes:

• Using non-existent toSequence() on arrays
• Confusing sequenceOf() with sequence()
• Trying to create sequence directly from array without conversion

2. Which of the following is the correct syntax to create a sequence from a range in Kotlin?

easy

A. val seq = (1..5).toSequence()

B. val seq = sequence(1..5)

C. val seq = (1..5).asSequence()

D. val seq = sequenceOf(1..5)

Solution

1. Step 1: Identify how to convert a range to a sequence

   Ranges in Kotlin can be converted to sequences using the asSequence() extension function.

2. Step 2: Evaluate each option's syntax

   val seq = (1..5).asSequence() uses (1..5).asSequence(), which is correct. val seq = (1..5).toSequence() uses toSequence() which does not exist for ranges. val seq = sequence(1..5) uses sequence(1..5) which is invalid syntax. val seq = sequenceOf(1..5) creates a sequence of a single range object, not elements.

3. Final Answer:

   val seq = (1..5).asSequence() -> Option C

4. Quick Check:

   Range to sequence = asSequence() [OK]

Hint: Use asSequence() to convert ranges to sequences [OK]

Common Mistakes:

• Using toSequence() which does not exist
• Passing range directly to sequence() function
• Using sequenceOf() with a range as single element

3. What will be the output of the following Kotlin code?

val seq = generateSequence(1) { it + 2 }.take(4).toList()
println(seq)

medium

A. [1, 3, 5, 7]

B. [1, 2, 3, 4]

C. [2, 4, 6, 8]

D. [1, 3, 5]

Solution

1. Step 1: Understand generateSequence with lambda

   The sequence starts at 1, then each next element is previous + 2, so elements are 1, 3, 5, 7, ...

2. Step 2: Apply take(4) and convert to list

   Taking first 4 elements gives [1, 3, 5, 7]. Printing this list outputs exactly that.

3. Final Answer:

   [1, 3, 5, 7] -> Option A

4. Quick Check:

   Sequence increments by 2 starting at 1 = [1, 3, 5, 7] [OK]

Hint: generateSequence(start) { it + step } creates arithmetic sequence [OK]

Common Mistakes:

• Confusing take(4) with takeWhile
• Assuming sequence increments by 1 instead of 2
• Forgetting to convert sequence to list before printing

4. Identify the error in the following Kotlin code that tries to create a sequence of even numbers starting from 2:

val seq = generateSequence(2) { it + 2 }
val firstThree = seq.take(3).toList()
println(firstThree)

medium

A. generateSequence requires a nullable lambda return type

B. take() does not exist for sequences

C. toList() cannot be called on a sequence

D. No error; code works correctly

Solution

1. Step 1: Check generateSequence usage

   The code uses generateSequence with a start value and lambda to add 2 each time, which is valid.

2. Step 2: Verify take() and toList() usage

   Sequences support take() to limit elements and toList() to convert to list. Both are valid here.

3. Final Answer:

   No error; code works correctly -> Option D

4. Quick Check:

   generateSequence + take + toList = valid sequence creation [OK]

Hint: generateSequence with non-null lambda works fine [OK]

Common Mistakes:

• Thinking lambda must return nullable type
• Believing toList() is invalid on sequences
• Assuming take() is not available for sequences

5. You want to create a sequence of Fibonacci numbers up to 100 using generateSequence. Which of the following code snippets correctly implements this?

hard

A. val fibSeq = generateSequence(0) { it + it - 1 }
val result = fibSeq.takeWhile { it <= 100 }.toList()

B. val fibSeq = generateSequence(Pair(0, 1)) { (a, b) -> if (b <= 100) Pair(b, a + b) else null }
val result = fibSeq.map { it.first }.toList()

C. val fibSeq = sequenceOf(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144)
val result = fibSeq.filter { it <= 100 }.toList()

D. val fibSeq = generateSequence(0 to 1) { (a, b) -> Pair(b, a + b) }
val result = fibSeq.map { it.second }.takeWhile { it <= 100 }.toList()

Solution

1. Step 1: Understand Fibonacci sequence generation with generateSequence

   We use a Pair to hold two consecutive Fibonacci numbers. The lambda returns next pair if next number is ≤ 100, else null to stop.

2. Step 2: Analyze each option

   val fibSeq = generateSequence(Pair(0, 1)) { (a, b) -> if (b <= 100) Pair(b, a + b) else null }
   val result = fibSeq.map { it.first }.toList()

   correctly uses Pair and stops at 100, then maps to first element for Fibonacci numbers.

   val fibSeq = generateSequence(0) { it + it - 1 }
   val result = fibSeq.takeWhile { it <= 100 }.toList()

   uses incorrect formula.

   val fibSeq = sequenceOf(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144)
   val result = fibSeq.filter { it <= 100 }.toList()

   hardcodes values but includes 144 which is > 100.

   val fibSeq = generateSequence(0 to 1) { (a, b) -> Pair(b, a + b) }
   val result = fibSeq.map { it.second }.takeWhile { it <= 100 }.toList()

   maps to second element and takes while ≤ 100, but first element 0 is missed and sequence never stops (infinite).

3. Final Answer:

   generateSequence(Pair(0, 1)) { (a, b) -> if (b <= 100) Pair(b, a + b) else null }.map { it.first }.toList() -> Option B

4. Quick Check:

   generateSequence with Pair and null stop = correct Fibonacci [OK]

Hint: Use Pair and null to stop generateSequence for Fibonacci [OK]

Common Mistakes:

• Not stopping sequence with null when limit exceeded
• Incorrect Fibonacci formula in lambda
• Including numbers beyond limit in hardcoded sequences