Extensions for DSL building in Kotlin - Time & Space Complexity

Time Complexity: Extensions for DSL building

O(n^2)

Understanding Time Complexity

When we use extensions to build DSLs in Kotlin, we want to know how the program's running time changes as we add more elements.

We ask: How does the time to build or process the DSL grow when the input size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Html {
    private val children = mutableListOf()
    fun body(block: Body.() -> Unit) {
        val body = Body()
        body.block()
        children.add(body.content)
    }
}

class Body {
    var content = ""
    fun p(text: String) { content += "
$text
" }
}

fun html(block: Html.() -> Unit): Html {
    val html = Html()
    html.block()
    return html
}

This code builds a simple HTML DSL using extensions and lambdas to add paragraphs inside a body.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding paragraphs by appending strings inside the p function.
• How many times: Once per paragraph added; each call appends to the content string but with increasing cost due to string immutability.

How Execution Grows With Input

Each paragraph added triggers a string append. Since strings are immutable, each append copies the current content (O(k) for the k-th append).

Input Size (n)	Approx. Total Operations
10	55
100	5,050
1000	500,500

Pattern observation: The total work grows quadratically with the number of paragraphs added.

Final Time Complexity

Time Complexity: O(n2)

This means the time to build the DSL grows quadratically with the number of elements added.

Common Mistake

[X] Wrong: "Using extensions for DSL building always makes the code run instantly regardless of input size."

[OK] Correct: Even with extensions, each added element requires work, so time grows with input size.

Interview Connect

Understanding how DSL building scales helps you explain how your code handles more data gracefully and shows you think about performance in real projects.

Self-Check

What if we changed the string concatenation in p to use a StringBuilder? How would the time complexity change?