Why collections over arrays in C Sharp (C#) - Performance Analysis

Time Complexity: Why collections over arrays

O(n)

Understanding Time Complexity

We want to understand how using collections instead of arrays affects the time it takes to do common tasks.

How does the choice between arrays and collections change the work done as data grows?

Scenario Under Consideration

Analyze the time complexity of adding elements to an array versus a List<T> collection.

int[] numbers = new int[5];
for (int i = 0; i < 5; i++)
{
    numbers[i] = i;
}

List<int> numberList = new List<int>();
for (int i = 0; i < 5; i++)
{
    numberList.Add(i);
}
    

This code fills a fixed-size array and a dynamic list with 5 numbers each.

Identify Repeating Operations

Look at the loops and operations that repeat as we add items.

• Primary operation: Assigning or adding an element inside a loop.
• How many times: Exactly 5 times for both array and list in this example.

How Execution Grows With Input

As we add more items, the array assignment stays simple but the list may need extra work.

Input Size (n)	Approx. Operations for Array	Approx. Operations for List
10	10 assignments	About 10 adds, some resizing
100	100 assignments	About 100 adds, several resizes
1000	1000 assignments	About 1000 adds, multiple resizes

Array operations grow directly with input size. List operations also grow but resizing causes extra work sometimes.

Final Time Complexity

Time Complexity: O(n)

This means both array and list take time proportional to the number of items added, but lists handle resizing behind the scenes.

Common Mistake

[X] Wrong: "Adding to a List is always slower than arrays because of resizing overhead."

[OK] Correct: Lists resize only occasionally, so most adds are fast. Over many adds, the average time per add stays low.

Interview Connect

Understanding how collections manage time costs helps you explain why they are often preferred over arrays for flexible data. This skill shows you think about efficiency and practical coding.

Self-Check

What if we changed the List to a LinkedList? How would the time complexity of adding elements change?