SelectMany for flattening in C Sharp (C#) - Time & Space Complexity

Time Complexity: SelectMany for flattening

O(n)

Understanding Time Complexity

When we use SelectMany to flatten collections, we want to know how the time to run grows as the input grows.

We ask: How does the number of operations change when the input lists get bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

var listOfLists = new List<List<int>> {
    new List<int> {1, 2, 3},
    new List<int> {4, 5},
    new List<int> {6}
};

var flattened = listOfLists.SelectMany(innerList => innerList).ToList();
    

This code takes a list of lists of numbers and combines all inner lists into one single list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Going through each inner list and then each item inside it.
• How many times: Once for every item inside every inner list combined.

How Execution Grows With Input

Imagine the total number of items inside all inner lists combined is n.

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

Pattern observation: The work grows directly with the total number of items to flatten.

Final Time Complexity

Time Complexity: O(n)

This means the time to flatten grows in a straight line with the total number of items inside all lists.

Common Mistake

[X] Wrong: "SelectMany runs in constant time no matter how big the lists are."

[OK] Correct: Actually, SelectMany must look at every item to combine them, so time grows with total items.

Interview Connect

Understanding how flattening collections scales helps you explain efficiency clearly and shows you know how data size affects performance.

Self-Check

"What if the inner lists were all empty except one very large list? How would the time complexity change?"