Generic class declaration in Kotlin - Time & Space Complexity

Time Complexity: Generic class declaration

O(n)

Understanding Time Complexity

Let's see how the time needed to create and use a generic class changes as we add more items.

We want to know how the program's work grows when the number of stored items grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Box<T> {
    private val items = mutableListOf<T>()

    fun add(item: T) {
        items.add(item)
    }

    fun get(index: Int): T {
        return items[index]
    }
}
    

This code defines a generic Box class that can hold items of any type. It adds items and gets them by index.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding an item to the list and accessing an item by index.
• How many times: Each add or get is done once per call, no loops inside these methods.

How Execution Grows With Input

Adding or getting one item takes about the same time no matter how many items are in the box.

Input Size (n)	Approx. Operations
10	10 adds = 10 operations
100	100 adds = 100 operations
1000	1000 adds = 1000 operations

Pattern observation: The work grows directly with the number of items added, one operation per item.

Final Time Complexity

Time Complexity: O(n)

This means the time to add n items grows in a straight line with n; each item takes about the same time.

Common Mistake

[X] Wrong: "Adding an item takes longer as the box gets full because it has to check all items."

[OK] Correct: The list adds items at the end quickly without checking all items, so each add takes about the same time.

Interview Connect

Understanding how generic classes handle data helps you explain how your code scales when storing many items, a useful skill in many coding tasks.

Self-Check

"What if the get method searched for an item by value instead of using an index? How would the time complexity change?"