Building blocks of type-safe builders in Kotlin - Time & Space Complexity

Time Complexity: Building blocks of type-safe builders

O(n)

Understanding Time Complexity

When we build type-safe builders in Kotlin, we want to know how the time it takes to run grows as we add more elements or nested blocks.

We ask: How does the work increase when the builder handles more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class HtmlBuilder {
    private val children = mutableListOf()

    fun element(name: String, block: HtmlBuilder.() -> Unit) {
        val childBuilder = HtmlBuilder()
        childBuilder.block()
        children.add("<$name>${childBuilder.render()}</$name>")
    }

    fun render(): String = children.joinToString("")
}

This code builds nested HTML elements by calling element blocks and collecting their rendered strings.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calling element recursively to build nested elements.
• How many times: Once per element added, plus the join operation over all children when rendering.

How Execution Grows With Input

As you add more elements, the builder calls itself for each nested block and then joins all children strings.

Input Size (n)	Approx. Operations
10	About 10 recursive calls and joining 10 strings
100	About 100 recursive calls and joining 100 strings
1000	About 1000 recursive calls and joining 1000 strings

Pattern observation: The work grows roughly in direct proportion to the number of elements added.

Final Time Complexity

Time Complexity: O(n)

This means the time to build and render grows linearly with the number of elements.

Common Mistake

[X] Wrong: "Because of recursion, the time must grow much faster than the number of elements."

[OK] Correct: Each element calls the builder once, so the total calls equal the number of elements, not more. The recursion depth does not multiply work exponentially.

Interview Connect

Understanding how recursive builders scale helps you explain your code's efficiency clearly and confidently in interviews.

Self-Check

"What if the render method joined children strings inside each recursive call instead of once at the end? How would the time complexity change?"