Flat_map for nested flattening in Ruby - Time & Space Complexity

Time Complexity: Flat_map for nested flattening

O(n)

Understanding Time Complexity

We want to understand how the time it takes to flatten nested lists using flat_map grows as the input gets bigger.

Specifically, how does the number of operations change when we use flat_map on nested arrays?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

nested = [[1, 2], [3, 4], [5, 6]]
flat = nested.flat_map { |sub_array| sub_array.map { |x| x * 2 } }

This code doubles each number inside nested arrays and flattens the result into one array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Iterating over each sub-array and then each element inside it.
• How many times: For each element in all nested arrays combined, the block runs once.

How Execution Grows With Input

As the total number of elements inside all nested arrays grows, the work grows roughly the same amount.

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

Pattern observation: The operations grow linearly with the total number of elements.

Final Time Complexity

Time Complexity: O(n)

This means the time to flatten and process grows directly in proportion to the total number of elements.

Common Mistake

[X] Wrong: "Using flat_map is slower because it has to flatten, so it must be more than linear time."

[OK] Correct: The flattening happens as part of one pass over all elements, so it still only touches each element once, keeping the time linear.

Interview Connect

Understanding how flat_map works helps you explain how nested data can be handled efficiently, a useful skill in many coding tasks.

Self-Check

What if we replaced flat_map with separate map and flatten calls? How would the time complexity change?