Async coroutine builder in Kotlin - Time & Space Complexity

Time Complexity: Async coroutine builder

O(n)

Understanding Time Complexity

When using async coroutine builders, it's important to understand how the program's work grows as you start more asynchronous tasks.

We want to know how the time to complete changes when we launch many async operations.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import kotlinx.coroutines.*

fun main() = runBlocking {
    val n = 10
    val deferredList = (1..n).map { i ->
        async {
            delay(100L) // simulate work
            i * 2
        }
    }
    val results = deferredList.awaitAll()
    println(results)
}
    

This code launches n async coroutines that each wait a bit and then return a value. It collects all results at the end.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Launching n async coroutines inside a map loop.
• How many times: Exactly n times, once per item.

How Execution Grows With Input

Each async coroutine runs independently, so the total work grows with how many coroutines you start.

Input Size (n)	Approx. Operations
10	10 async tasks launched
100	100 async tasks launched
1000	1000 async tasks launched

Pattern observation: The number of async tasks grows directly with n, so the work grows linearly.

Final Time Complexity

Time Complexity: O(n)

This means the total time to launch and wait for all async tasks grows in a straight line as you add more tasks.

Common Mistake

[X] Wrong: "Async coroutines always run instantly and don't add to total time."

[OK] Correct: Even though async tasks run concurrently, starting and waiting for many tasks still takes more time as you add more tasks.

Interview Connect

Understanding how async tasks scale helps you write efficient concurrent programs and explain your reasoning clearly in interviews.

Self-Check

What if we changed delay(100L) to a CPU-heavy calculation inside each async block? How would the time complexity change?