List generic collection in C Sharp (C#) - Time & Space Complexity

Time Complexity: List generic collection

O(n)

Understanding Time Complexity

When working with a List in C#, it's important to know how the time to do actions changes as the list grows.

We want to understand how fast operations like adding or searching items happen as the list gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

List<int> numbers = new List<int>();
for (int i = 0; i < n; i++)
{
    numbers.Add(i);
}
int index = numbers.IndexOf(target);
    

This code adds numbers from 0 to n-1 into a list, then searches for a target number's position.

Identify Repeating Operations

• Primary operation: Adding items in a loop and searching through the list.
• How many times: Adding happens n times; searching may check up to n items.

How Execution Grows With Input

Adding items grows roughly in a straight line with n, because each add is quick most times.

Searching grows in a straight line too, because it may check each item until it finds the target.

Input Size (n)	Approx. Operations
10	About 10 adds, up to 10 checks to find target
100	About 100 adds, up to 100 checks to find target
1000	About 1000 adds, up to 1000 checks to find target

Pattern observation: Both adding and searching grow linearly as the list size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to add or search grows directly with the number of items in the list.

Common Mistake

[X] Wrong: "Adding items to a List always takes the same time no matter how big it is."

[OK] Correct: Most adds are fast, but sometimes the list needs to resize its storage, which takes more time.

Interview Connect

Understanding how List operations scale helps you explain your choices clearly and shows you know how data grows in real programs.

Self-Check

"What if we used a LinkedList instead of a List? How would the time complexity for adding and searching change?"