Multiple type parameters in Kotlin - Time & Space Complexity

Time Complexity: Multiple type parameters

O(n * m)

Understanding Time Complexity

When using multiple type parameters in Kotlin, we want to understand how the program's work grows as input sizes change.

We ask: how does the time needed change when the inputs for each type grow?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fun <A, B> pairElements(listA: List<A>, listB: List<B>): List<Pair<A, B>> {
    val result = mutableListOf<Pair<A, B>>()
    for (a in listA) {
        for (b in listB) {
            result.add(Pair(a, b))
        }
    }
    return result
}
    

This function creates pairs from every element in listA with every element in listB.

Identify Repeating Operations

• Primary operation: Nested loops over listA and listB.
• How many times: Outer loop runs once per element in listA; inner loop runs once per element in listB for each outer loop.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
listA = 10, listB = 10	100
listA = 100, listB = 100	10,000
listA = 1000, listB = 1000	1,000,000

Pattern observation: The total work grows by multiplying the sizes of both lists.

Final Time Complexity

Time Complexity: O(n * m)

This means the time needed grows by multiplying the size of the first list (n) by the size of the second list (m).

Common Mistake

[X] Wrong: "The time grows only with the size of one list because the other is just a type parameter."

[OK] Correct: Both lists have real sizes that affect the loops. The type parameters only name the types, but the loops run over actual elements, so both sizes matter.

Interview Connect

Understanding how multiple inputs affect time helps you explain your code clearly and shows you can think about efficiency in real situations.

Self-Check

"What if we changed the inner loop to only run a fixed number of times regardless of listB's size? How would the time complexity change?"