Star projection for unknown types in Kotlin - Time & Space Complexity

Time Complexity: Star projection for unknown types

O(n)

Understanding Time Complexity

When using star projections in Kotlin generics, it's important to understand how the program's work changes as input grows.

We want to see how the unknown type affects the number of operations the program does.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fun printListSize(list: List<*>) {
    println("Size: ${list.size}")
    for (item in list) {
        println(item)
    }
}

fun main() {
    val numbers: List = listOf(1, 2, 3, 4, 5)
    printListSize(numbers)
}
    

This code prints the size and all elements of a list with an unknown type using star projection.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each element in the list.
• How many times: Once for each element in the list (n times).

How Execution Grows With Input

As the list gets bigger, the program prints more items, so the work grows with the list size.

Input Size (n)	Approx. Operations
10	About 10 prints plus 1 size check
100	About 100 prints plus 1 size check
1000	About 1000 prints plus 1 size check

Pattern observation: The number of operations grows roughly in direct proportion to the list size.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows linearly with the number of items in the list.

Common Mistake

[X] Wrong: "Using star projection makes the code slower or more complex."

[OK] Correct: Star projection only hides the exact type but does not add extra loops or slow down the code. The main work still depends on the list size.

Interview Connect

Understanding how unknown types affect performance helps you write clear and efficient generic code, a useful skill in many coding tasks.

Self-Check

"What if we changed the list to a nested list like List<List<*>>? How would the time complexity change?"