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?"

Practice

1. What does the star projection * represent in Kotlin generics?

easy

A. A type that can only be used with primitive data types

B. A specific generic type that must be defined explicitly

C. A wildcard that allows writing but restricts reading

D. An unknown generic type that allows safe reading but restricts writing

Solution

1. Step 1: Understand star projection meaning

   The star projection * means an unknown generic type in Kotlin.

2. Step 2: Analyze its usage

   It allows safe reading from generic collections but restricts writing to avoid type errors.

3. Final Answer:

   An unknown generic type that allows safe reading but restricts writing -> Option D

4. Quick Check:

   Star projection = unknown generic type with safe read [OK]

Hint: Star projection means unknown type, safe read only [OK]

Common Mistakes:

• Thinking star projection allows writing to generics
• Confusing star projection with specific generic types
• Assuming star projection only works with primitives

2. Which of the following is the correct syntax to declare a list with star projection in Kotlin?

easy

A. val list: List<Any> = listOf(1, 2, 3)

B. val list: List<*> = listOf(1, 2, 3)

C. val list: List<> = listOf(1, 2, 3)

D. val list: List = listOf(1, 2, 3)

Solution

1. Step 1: Recall star projection syntax

   Star projection uses * inside angle brackets to represent unknown type.

2. Step 2: Check each option

   val list: List<*> = listOf(1, 2, 3) uses List<*> which is correct syntax for star projection.

3. Final Answer:

   val list: List<*> = listOf(1, 2, 3) -> Option B

4. Quick Check:

   Star projection syntax = List<*> [OK]

Hint: Star projection syntax always uses * inside angle brackets [OK]

Common Mistakes:

• Leaving angle brackets empty like List<>
• Using List<Any> which is not star projection
• Confusing star projection with out-projection

3. What will be the output of the following Kotlin code?

fun printFirst(list: List<*>) {
    println(list[0])
}

fun main() {
    val numbers: List<Int> = listOf(10, 20, 30)
    printFirst(numbers)
}

medium

A. 10

B. Compilation error

C. null

D. Runtime exception

Solution

1. Step 1: Understand star projection usage in function

   The function accepts List<*>, meaning unknown generic type, safe to read elements.

2. Step 2: Analyze the call with List<Int>

   Passing List<Int> is valid; reading list[0] returns 10 safely.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Reading from List<*> returns element safely [OK]

Hint: Reading from List<*> works, writing does not [OK]

Common Mistakes:

• Assuming star projection causes compile error
• Expecting null instead of actual element
• Thinking runtime exception occurs on read

4. Identify the error in the following Kotlin code using star projection:

fun addElement(list: MutableList<*>, element: Any) {
    list.add(element)
}

medium

A. Element type Any is incompatible with list

B. Syntax error in function declaration

C. Cannot add element to MutableList<*> due to unknown type

D. No error, code compiles and runs fine

Solution

1. Step 1: Understand star projection with MutableList

   MutableList<*> means unknown generic type; writing is restricted to avoid type errors.

2. Step 2: Analyze the add operation

   Trying to add element causes compile error because type is unknown and unsafe to write.

3. Final Answer:

   Cannot add element to MutableList<*> due to unknown type -> Option C

4. Quick Check:

   Writing to MutableList<*> causes error [OK]

Hint: Cannot write to star-projected mutable collections [OK]

Common Mistakes:

• Thinking add works with MutableList<*>
• Confusing syntax error with type error
• Assuming Any type is always accepted

5. Given a function that accepts a list with star projection, how can you safely copy elements from List<*> to a MutableList<Any> in Kotlin?

hard

A. Use a loop to cast each element to Any and add to MutableList<Any>

B. Directly assign List<*> to MutableList<Any>

C. Use star projection on both lists

D. Use MutableList<*> instead of MutableList<Any>

Solution

1. Step 1: Understand star projection restrictions

   List<*> allows safe reading but elements are of unknown type, so direct assignment to MutableList<Any> is unsafe.

2. Step 2: Safely copy elements

   Use a loop to read each element and cast to Any before adding to MutableList<Any>, ensuring type safety.

3. Final Answer:

   Use a loop to cast each element to Any and add to MutableList<Any> -> Option A

4. Quick Check:

   Copy with loop and cast = safe transfer [OK]

Hint: Copy elements with loop and cast from List<*> to MutableList<Any> [OK]

Common Mistakes:

• Trying direct assignment between incompatible generic types
• Using star projection on mutable list incorrectly
• Ignoring type casting when copying elements