Generic interface for collections in Typescript - Time & Space Complexity

Time Complexity: Generic interface for collections

O(n)

Understanding Time Complexity

When working with generic interfaces for collections, it's important to know how the time to perform actions changes as the collection grows.

We want to find out how the number of steps grows when we add or check items in the collection.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

interface Collection<T> {
  add(item: T): void;
  contains(item: T): boolean;
}

class SimpleCollection<T> implements Collection<T> {
  private items: T[] = [];

  add(item: T): void {
    this.items.push(item);
  }

  contains(item: T): boolean {
    return this.items.includes(item);
  }
}
    

This code defines a generic collection interface and a simple class that stores items in an array. It adds items and checks if an item exists.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The contains method uses includes, which checks each item one by one.
• How many times: It may check up to all items in the array, depending on where the item is found.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The number of checks grows directly with the number of items. More items mean more steps to find one.

Final Time Complexity

Time Complexity: O(n)

This means the time to check if an item exists grows in a straight line with the number of items in the collection.

Common Mistake

[X] Wrong: "Checking if an item exists is always fast and takes the same time no matter how many items there are."

[OK] Correct: Because the method checks items one by one, more items mean more checks, so it takes longer as the collection grows.

Interview Connect

Understanding how generic collections work and how their operations scale helps you explain your code choices clearly and confidently in real projects and interviews.

Self-Check

"What if we changed the internal storage from an array to a Set? How would the time complexity of contains change?"