Collection functions (length, flatten, merge) in Terraform - Time & Space Complexity

Time Complexity: Collection functions (length, flatten, merge)

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run collection functions changes as the size of the collections grows.

How does the work grow when we use length, flatten, or merge on bigger lists or maps?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

locals {
  list_of_lists = [[1, 2], [3, 4], [5, 6]]
  merged_map   = merge({a = 1}, {b = 2}, {c = 3})
  flat_list    = flatten(local.list_of_lists)
  list_length  = length(local.flat_list)
}
    

This code merges maps, flattens a list of lists into a single list, and finds the length of the flattened list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing each element in the lists or maps to merge or flatten.
• How many times: Each element is visited once during flatten or merge.

How Execution Grows With Input

As the number of elements in the collections grows, the work grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	About 10 steps to process all elements
100	About 100 steps
1000	About 1000 steps

Pattern observation: Doubling the input roughly doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to run these functions grows linearly with the size of the input collections.

Common Mistake

[X] Wrong: "Flatten or merge runs instantly no matter how big the input is."

[OK] Correct: These functions must look at each element to combine or flatten, so bigger inputs take more time.

Interview Connect

Understanding how collection functions scale helps you write efficient Terraform code and explain your reasoning clearly in interviews.

Self-Check

"What if we nested lists three levels deep and used flatten multiple times? How would the time complexity change?"