Foreach loop over collections in C Sharp (C#) - Time & Space Complexity

Time Complexity: Foreach loop over collections

O(n)

Understanding Time Complexity

When we use a foreach loop to go through a collection, we want to know how the time it takes changes as the collection grows.

We ask: How does the number of steps grow when the collection gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

List numbers = new List {1, 2, 3, 4, 5};
int sum = 0;
foreach (int num in numbers)
{
    sum += num;
}
Console.WriteLine(sum);
    

This code adds up all numbers in a list using a foreach loop.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The foreach loop that visits each item in the list.
• How many times: Once for every item in the list.

How Execution Grows With Input

As the list gets bigger, the loop runs more times, one for each item.

Input Size (n)	Approx. Operations
10	10 steps
100	100 steps
1000	1000 steps

Pattern observation: The number of steps grows directly with the size of the list.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line as the list gets bigger.

Common Mistake

[X] Wrong: "The foreach loop runs in constant time no matter how big the list is."

[OK] Correct: The loop must visit each item, so if the list doubles, the loop runs twice as many times.

Interview Connect

Understanding how loops grow with input size helps you explain your code clearly and shows you know how programs behave with bigger data.

Self-Check

"What if we replaced the foreach loop with two nested foreach loops over the same list? How would the time complexity change?"